Advanced String Manipulation

Strings are not prose

The phrase "string manipulation" usually conjures up concatenation, case conversion, and a few regex tricks. That is the applied surface. Underneath sits a much richer subject: the theory of sequences drawn from a finite alphabet, with its own canon of algorithms and its own characteristic running times. Most production code never reaches for this canon, because the str methods in the standard library are enough. But when a problem asks for the longest repeating substring in a million characters, or whether a pattern appears in streamed text without buffering all of it, the library stops helping and the algorithms take over.

The organising principle of this module is the interaction between local operations (compare two characters) and global questions (does pattern P occur in text T?). Every algorithm worth learning is a clever way of answering a global question by doing only locally-cheap work.

Character counts and the 128-slot array

The simplest "algorithmic" string technique is also the most commonly useful. For any problem that asks about character frequency within a known alphabet, a fixed-size integer array beats a hash map on both time and clarity:

def is_anagram(a, b):
    if len(a) != len(b): return False
    counts = [0] * 128   # ASCII range
    for ch in a: counts[ord(ch)] += 1
    for ch in b:
        counts[ord(ch)] -= 1
        if counts[ord(ch)] < 0: return False
    return True

One pass each, constant extra memory (128 integers is constant; it does not grow with input), and no hash overhead. When someone writes this with a Counter, they are paying a 2× constant for no algorithmic gain.

Rolling hashes

A string s[0..k) can be treated as the integer s[0]·B^(k-1) + s[1]·B^(k-2) + ... + s[k-1]·B^0, taken modulo a large prime. Shifting the window one character to the right updates the hash in constant time: subtract the contribution of the character falling out, multiply by B, add the new character. That single trick reduces an O(n·k) substring-match to O(n):

MOD = (1 << 61) - 1
B   = 131

def rolling_hashes(s, k):
    h = 0
    power = pow(B, k, MOD)
    for i, ch in enumerate(s):
        h = (h * B + ord(ch)) % MOD
        if i >= k - 1:
            yield i - k + 1, h
            # remove the character that's leaving the window
            # (equivalent to: h = h - ord(s[i-k+1]) * power)
            # done implicitly by the next multiply-and-add

Two practical notes. First, a single 64-bit hash is probably unique; a determined adversary can construct collisions. In interview contexts one is fine; in production, use two hashes with different bases and primes and accept O(n) time proportional to verified matches. Second, the modulus must be a prime well above the alphabet size to keep the distribution uniform. 2^61 − 1 is a Mersenne prime and plays well with Python's arbitrary-precision integers; for fixed-width languages, the 32-bit prime 10^9 + 7 is traditional.

KMP: pattern matching without hashing

Knuth-Morris-Pratt solves the same problem as Rabin-Karp (find all occurrences of pattern P in text T) in deterministic O(n + m), without any hashing and without any probability of error. The idea is to precompute, for each position i in P, the length of the longest proper prefix of P[0..i] that is also a suffix. When matching fails at position j in the pattern, that table tells you the longest continuation that is still consistent with the characters already seen, so you never re-examine a text character.

KMP is worth internalising because the failure-function construction is the same shape as the matching loop. Once you see it written twice, it lodges in memory.

Palindromes & the expand-around-centre trick

For "longest palindromic substring" in O(n²), expand around every possible centre. There are 2n−1 centres (one between each pair of adjacent characters, plus one on each character), and expansion is O(n) per centre in the worst case, giving O(n²) total. That is good enough for interviews and most production use. Manacher's algorithm does it in O(n), but the constant and the code complexity make it worth learning only when you need it.

def longest_palindrome(s):
    def expand(l, r):
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1; r += 1
        return s[l+1:r]
    best = ""
    for i in range(len(s)):
        a = expand(i, i)        # odd length
        b = expand(i, i + 1)    # even length
        if len(a) > len(best): best = a
        if len(b) > len(best): best = b
    return best

Sliding windows over strings

The "longest substring with at most k distinct characters" problem, the "minimum window substring" problem, and the "find all anagrams of P in T" problem are all instances of the same template: maintain a frequency count for the window, expand the right edge, contract the left edge whenever the window violates the invariant, record the best window whenever it satisfies the target. The concept page walks through three of these with complexity proofs.

Complexities, reasoned

Character-count anagrams: O(n), O(σ) where σ is alphabet size. Naive substring matching: O(n·m). Rabin-Karp: O(n + m) expected, O(n·m) worst-case adversarial. KMP: O(n + m) deterministic, O(m) preprocessing. Longest palindromic substring: O(n²) via expand-around-centre, O(n) via Manacher. Longest common subsequence: O(n·m) via dynamic programming, and this is known to be tight under the Strong Exponential Time Hypothesis. If you need faster than quadratic, you need a different problem.

When alphabet-aware code pays off

If the input is ASCII or lowercase letters, the 128- or 26-slot array is faster, simpler, and less error-prone than a hash map. If the input is arbitrary Unicode, you must use a hash map, and you must think carefully about normalisation, because "é" can be one codepoint or two. For binary data treated as bytes, the 256-slot array is the natural tool. Reach for rolling hashes only when a single pattern does not suffice; for one-shot matching, str.find is already O(n + m) in any reasonable standard library.

Where beginners go wrong

• Using a hash map when an array suffices. 26 or 128 counts beat a dict on constants and clarity. The hash map is not a default; it's the fallback when the alphabet is large.
• Treating Unicode as ASCII. len(s) on a string with combining characters or emoji does not count glyphs. For algorithms, use codepoints explicitly and normalise first.
• Single-hash Rabin-Karp in adversarial settings. A contestant-crafted input can force collisions. Double hashing eliminates this; single hashing is fine only when the adversary does not exist.
• Expanding around every position including the end. The palindrome expansion has two kinds of centres; forgetting the even-length case misses palindromes like "abba".

What to read next

Continue with Module 04 · Hash Maps & Sets, which formalises the data structure you've been using implicitly. Or, for a deep dive into windowed counting, the concept page on Sliding Window in Depth is the most useful single-sitting read in this module's orbit.