📍 String Indexing & Slicing — Performance & Algorithms

Deep dive into string access patterns, algorithmic complexity, and optimization techniques.

🎯 Indexing Complexity & Bounds Checking

# Indexing is O(1) operation
text = "0123456789"
print(text[5])  # Direct access, constant time

# Python validates bounds
try:
    print(text[100])
except IndexError as e:
    print(f"Error: {e}")

# Negative indexing
print(text[-1])   # 9
print(text[-10])  # 0
print(text[-11])  # IndexError

# CPython optimization for common patterns
text = "x" * 1000000
first = text[0]      # O(1)
last = text[-1]      # O(1)
last_1000 = text[-1000:]  # O(n) - creates substring

💡 Slicing Performance Analysis

import sys
import timeit

# Slicing creates new string objects
text = "Hello World"
s1 = text[0:5]
s2 = text[0:5]
print(s1 == s2, s1 is s2)  # True, False

# Memory implications
large = "x" * 1000000
slice1 = large[0:100]      # 100-byte string
slice2 = large[900000:]    # 100,000-byte string

print(sys.getsizeof(slice1))
print(sys.getsizeof(slice2))

# Slicing complexity is O(n) where n = slice length
def slice_time(size, slice_len):
    text = "x" * size
    return timeit.timeit(lambda: text[0:slice_len], number=1000)

# Larger slices take more time
print(slice_time(10000, 100))    # Small slice
print(slice_time(10000, 5000))   # Large slice

🎨 Stride Slicing Patterns

# Basic stride
text = "0123456789"
print(text[::2])    # 02468 (every 2nd)
print(text[1::2])   # 13579 (odd indices)
print(text[::3])    # 0369 (every 3rd)

# Reverse with stride
print(text[::-1])   # 9876543210
print(text[::-2])   # 97531 (reverse, every 2nd)

# Custom starting point with reverse
print(text[8:2:-1]) # 87654

# Window extraction
def get_windows(text, size):
    """Extract all windows of given size"""
    return [text[i:i+size] for i in range(len(text) - size + 1)]

print(get_windows("ABCDE", 3))
# ['ABC', 'BCD', 'CDE']

# Optimized window extraction
def get_windows_optimized(text, size):
    """Vectorized window extraction"""
    # More memory efficient for certain operations
    for i in range(len(text) - size + 1):
        yield text[i:i+size]

📊 String Searching Algorithms

# Linear search (naive)
def find_substring_naive(text, pattern):
    """O(n*m) naive string search"""
    for i in range(len(text) - len(pattern) + 1):
        if text[i:i+len(pattern)] == pattern:
            return i
    return -1

# Using built-in (optimized - often Boyer-Moore or similar)
def find_substring_builtin(text, pattern):
    """O(n) typical case with optimized algorithm"""
    return text.find(pattern)

# KMP algorithm (O(n+m))
def build_kmp_table(pattern):
    """Build KMP failure function"""
    m = len(pattern)
    table = [0] * m
    j = 0

    for i in range(1, m):
        while j > 0 and pattern[i] != pattern[j]:
            j = table[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
        table[i] = j

    return table

def find_kmp(text, pattern):
    """KMP string search"""
    if not pattern:
        return 0

    table = build_kmp_table(pattern)
    j = 0

    for i in range(len(text)):
        while j > 0 and text[i] != pattern[j]:
            j = table[j - 1]
        if text[i] == pattern[j]:
            j += 1
        if j == len(pattern):
            return i - len(pattern) + 1

    return -1

# Compare performance
import timeit
text = "a" * 1000000 + "needle" + "a" * 1000000
pattern = "needle"

print(timeit.timeit(lambda: find_substring_builtin(text, pattern), number=10))
print(timeit.timeit(lambda: find_kmp(text, pattern), number=10))

💡 Index vs find() vs count()

# Performance differences
text = "hello hello hello"

# find() - returns index or -1
pos = text.find("hello")        # 0
print(pos)

# index() - returns index or raises error
try:
    pos = text.index("xyz")
except ValueError:
    print("Not found")

# count() - returns count
count = text.count("hello")     # 3

# Efficiency: count() must scan entire string
# find() returns after first match
# For multiple occurrences, count() is better than multiple find()

# Find all occurrences efficiently
def find_all(text, pattern):
    """Find all occurrences"""
    start = 0
    while True:
        pos = text.find(pattern, start)
        if pos == -1:
            break
        yield pos
        start = pos + 1

list(find_all("aaaa", "aa"))  # [0, 1, 2]

🔑 Key Takeaways

🔗 What's Next?

Learn advanced string method techniques.

Ready to practice? Challenges | Quiz