String Algorithms

Stop re-reading what you already know

Search for a needle made of 999 as followed by one b in a haystack of one million as. The needle never occurs, but the obvious search takes a long time to find that out. At each of the 999,001 possible start positions it matches 999 characters, fails on the b, shifts one place right and starts over. That is 999,001,000 character comparisons. A pure-Python version of that loop needs a few seconds for just the first 100,000 characters of the haystack (roughly 3 to 5 seconds, depending on the CPython version).

Comparing characters is cheap. The search is slow because after every failure it forgets what it just read. When the b fails, the search already knows that the last 999 text characters are all a, yet it reads them again from the next start. The KMP search in this lesson keeps that knowledge. It does the same job with about 3 million comparisons, in about a tenth of a second.

That is the idea of the whole lesson: fast string algorithms reuse what an earlier step already proved about the characters. Three tools do it in three different ways.

Throughout, n is the length of the text, m is the length of the pattern, and σ (sigma) is the number of different characters the input may contain.

Before you start. This lesson builds on Foundation: Arrays & Strings, which covers count vectors, building strings with join, and prefix sums. Checking whether one string is a palindrome, with two pointers, is in Palindrome Validation. Substring problems with a constraint ("longest substring with at most k distinct characters") belong to Sliding Window Patterns. Near the end, a routing table sends the other string problems to the lessons that own them.

What string operations really cost

A Python str is an immutable sequence of Unicode code points. Several innocent-looking operations hide a loop:

Use the built-in search in real code: on the needle-and-haystack example above, str.find answers in about half a millisecond. LeetCode 28's limits are small enough that the naive scan is accepted, but an interviewer may still ask you to build a linear-time matcher yourself, and the same machinery solves problems no built-in covers. Building a string with += in a loop is covered in the foundation lesson: collect the pieces in a list and join once.

Predict first: what does "aaaa".count("aa") return?

Move 1: Let the pattern say where to resume

Smell: after a partial match fails, the search shifts by one and re-reads text characters it has already matched.

LeetCode 28: Find the Index of the First Occurrence in a String asks for the first index where needle occurs in haystack, or −1. Here is the slow version:

def naive_find(text, pat):
    n, m = len(text), len(pat)
    for start in range(n - m + 1):
        j = 0
        while j < m and text[start + j] == pat[j]:
            j += 1
        if j == m:
            return start
    return -1

In the worst case it makes (n − m + 1) · m comparisons, which is the billion from the opening. Look at what it repeats. When the inner loop stops at j, it has just proved that text[start:start + j] == pat[:j]. The next start throws that proof away and reads the same text again.

Predict first: search for "ABABC" in "ABABABC". At start 0 the search matches ABAB, then text[4] = 'A' fails against 'C'. Without looking at the text again, which start positions can you rule out? At the first plausible start, how many pattern characters are already known to match?

Borders: the pattern overlapping itself

The answer came from the pattern alone: "ABAB" ends with "AB", and "AB" is also how the pattern begins. A border of a string is a proper prefix that is also a suffix. "Proper" means shorter than the whole string, since every string trivially matches itself. "ABAB" has the borders "AB" and the empty string. "ABA" has "A". "ABC" has only the empty border.

The prefix function records the longest border of every prefix of the pattern:

pi[i] = length of the longest border of pat[:i + 1]

The same array is also called the failure function or the LPS array (longest proper prefix that is also a suffix). For "ABABC" it is [0, 0, 1, 2, 0].

Here is how the search uses it. When a mismatch comes after j matched characters, slide the pattern until its longest border lines up with the end of the matched text, and continue with j = pi[j − 1]. Any alignment that overlaps the matched text needs that overlap to be a border, and the longest border gives the smallest shift. So no possible match is skipped. If the new character does not extend that border either, fall back to the next shorter one.

Building the table

def prefix_function(p):
    pi = [0] * len(p)
    k = 0                          # length of the border we are extending
    for i in range(1, len(p)):
        while k > 0 and p[i] != p[k]:
            k = pi[k - 1]          # fall back to the next shorter border
        if p[i] == p[k]:
            k += 1
        pi[i] = k
    return pi

The builder is the matcher run against the pattern itself. Entering step i, k is the longest border of p[:i], and the loop tries to extend it with p[i]. If p[i] does not fit, the next candidate is the longest border of that border, which is pi[k − 1]. That works because a border of a border is again a border, and every shorter border of p[:i] is found by following that chain.

Trace "ABACABAB":

Row 7 is the interesting one. The border "ABA" of "ABACABA" cannot be extended by B, because the character after it is C. The longest border of "ABA" is "A" (pi[2] = 1), and "A" followed by B is "AB", which fits. So pi[7] = 2, and the full table is [0, 0, 1, 0, 1, 2, 3, 2].

Searching

def kmp_find(text, pat):
    if not pat:
        return 0
    pi = prefix_function(pat)
    j = 0                          # pattern characters matched so far
    for i, ch in enumerate(text):
        while j > 0 and ch != pat[j]:
            j = pi[j - 1]          # keep the longest border, drop the rest
        if ch == pat[j]:
            j += 1
        if j == len(pat):
            return i - len(pat) + 1
    return -1

Trace the prediction example, pattern "ABABC" in text "ABABABC":

At i = 4 the mismatch drops j from 4 to pi[3] = 2. That is exactly "start 2, two characters known" from the prediction. Then text[4] extends the match to 3. The empty pattern returns 0, as str.find does.

Why it is correct and linear

Invariant: after processing text[i], j is the length of the longest prefix of pat that ends at text[i]. The fallback chain tries every border from longest to shortest, so the first one that the new character extends is the longest possible. Nothing longer was skipped.

Cost. j rises by at most 1 per text character, so it rises at most n times in the whole run. Every fallback lowers j by at least 1, and j never goes below 0. So the whole run has at most n fallbacks, even though a single character can trigger several of them. The search is O(n), the table costs O(m) by the same argument, and the total is O(n + m) time with O(m) extra space for pi. A text character can be compared more than once after fallbacks. What never happens is the text index moving backward. That is how a billion comparisons become about three million.

Traps

• Reset instead of fall back. Writing k = 0 in place of k = pi[k - 1] looks harmless and passes many tests. "AABAAB" gets [0, 1, 0, 1, 2, 3] either way. On "AABAAA", though, it returns [0, 1, 0, 1, 2, 1] instead of [0, 1, 0, 1, 2, 2]. After "AABAA", the next A does not extend the border "AA", and resetting throws away the shorter border "A", which it would have extended to "AA". Test patterns that need a second border.
• if instead of while. One fallback may not be enough. With if, "AAAB" gets pi[3] = 1 instead of 0: the code falls back once, from "AA" to "A", never checks again, and records a border that does not exist.
• pi[j] instead of pi[j − 1]. The table is indexed by the position of the last matched character, which is j − 1.
• Resetting after a full match. To report every occurrence, overlapping ones included, keep the border after a match instead of starting over:

def kmp_find_all(text, pat):       # pat must be non-empty
    pi = prefix_function(pat)
    hits, j = [], 0
    for i, ch in enumerate(text):
        while j > 0 and ch != pat[j]:
            j = pi[j - 1]
        if ch == pat[j]:
            j += 1
        if j == len(pat):
            hits.append(i - len(pat) + 1)
            j = pi[j - 1]          # a border of this match may start the next one
    return hits

kmp_find_all("aaaa", "aa") returns [0, 1, 2]. With j = 0 after a match, it returns [0, 2], the same undercount as str.count.

One table, several problems

• Borders of the whole string. pi[n − 1] is the longest border of the entire string. Then n − pi[n − 1] is its smallest period, the smallest shift p with s[i] == s[i + p] wherever both exist. The final round uses this.
• The concatenation trick. Compute the prefix function of pat + "#" + text. Wherever it equals m, a match of pat ends there. The separator must not occur in either string, or a border could run across it.
• Any sequence, not just strings. prefix_function only compares items for equality, so it runs unchanged on a list of integers or tuples. Some array problems turn into pattern matching once each element, or each step between neighbours, is encoded as a symbol.

Your turn: compute the prefix function of "abcabcab" by hand. What is the string's smallest period? Is it made of whole copies of one block?

def z_function(s):
    n = len(s)
    z = [0] * n
    left = right = 0               # s[left:right] matches the prefix s[0:right-left]
    for i in range(1, n):
        if i < right:
            z[i] = min(right - i, z[i - left])
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        if i + z[i] > right:
            left, right = i, i + z[i]
    return z

Move 2: Fingerprint the window, then roll it

Smell: the slow code compares or hashes every length-m window from scratch at O(m) each, although neighbouring windows share m − 1 characters.

A hash you can update in O(1)

Treat a window as a number written in base B, with its leftmost character as the most significant digit. With decimal digits this is literal: the length-3 windows of "31415" are 314, 141 and 415.

Predict first: compute 141 from 314 using only the digit that leaves (3) and the digit that enters (1).

For text, the digits are the code points ord(ch), the base B is a large number, and every step is reduced modulo a big prime M so the numbers stay small:

hash(w) = (w[0]·B^(m−1) + w[1]·B^(m−2) + … + w[m−1]) mod M
next    = ((hash − out·B^(m−1))·B + in) mod M

The Rabin–Karp search uses this rolling hash to decide which windows are worth checking:

import random

def rabin_karp_all(text, pat, base=None, mod=(1 << 61) - 1):
    n, m = len(text), len(pat)
    if m == 0 or m > n:
        return []
    if base is None:
        base = random.randrange(1 << 20, mod - 1)   # random base: no fixed input can target it
    high = pow(base, m - 1, mod)                    # weight of the character that leaves
    hp = hw = 0
    for i in range(m):
        hp = (hp * base + ord(pat[i])) % mod
        hw = (hw * base + ord(text[i])) % mod
    hits = []
    for start in range(n - m + 1):
        if hw == hp and text[start:start + m] == pat:   # equal hashes are a hint, not proof
            hits.append(start)
        if start + m < n:                               # roll: drop text[start], add text[start+m]
            hw = ((hw - ord(text[start]) * high) * base + ord(text[start + m])) % mod
    return hits

Equal hashes are a hint, not a proof

Reducing modulo M lets different windows land on the same value. With base 10 and M = 101, the windows "314", "213", "112" and "011" all hash to 11. So read a hash comparison in one direction only:

• Different hashes mean the strings are different. It is always safe to skip.
• Equal hashes mean the strings are probably equal. Compare the actual characters before reporting a match.

With that check, the answer is always correct; the hash only decides where to look. How often does it cry wolf? For two different windows, the difference of their hashes is a nonzero polynomial in B of degree at most m − 1. Modulo a prime, such a polynomial has at most m − 1 roots, so for a random B the chance of a collision is about m/M. With M = 2⁶¹ − 1 (a prime) and m = 10⁵, that is below 10⁻¹³.

Cost. Hashing the pattern and the first window is O(m). Each roll is O(1), and each verification is O(m). When true matches are rare, the expected total is O(n + m). When they are common, verification dominates. For text "a" * 100_000 and pattern "a" * 1_000, every one of the 99,001 windows is a real match and is verified character by character, which is about 10⁸ comparisons. KMP reports the same 99,001 positions in O(n + m). For finding one pattern, KMP's guarantee is better. Rolling hashes shine elsewhere: comparing windows with each other (repeats), checking many patterns of one length at once (put their hashes in a set), and comparing arbitrary substrings in O(1), shown below.

⚠️ Choose the base at random. A fixed, publicly known hash can be attacked. The classic example is base 31 with arithmetic modulo 2⁶⁴ (what C++ unsigned overflow gives you), which inputs built from the Thue–Morse sequence force into collisions. A random base with a large prime modulus leaves no input that was fixed in advance able to aim at your hash.

⚠️ Language differences. In Python, x % M lies in [0, M) whenever M is positive, even when x is negative, so the subtraction in the roll needs no fix. In Java and C++, % keeps the sign of x, so a stored hash can come out negative. It is still the right value modulo M, but it no longer equals the pattern's non-negative hash, and real matches are silently missed. Adding M once before % is not enough, because the unreduced value can lie far below −M. Normalise after the remainder instead: ((x % M) + M) % M. Python integers never overflow. In Java or C++, a product of two numbers near 2⁶¹ overflows 64 bits, so use 128-bit multiplication or a modulus below 2³¹. With a modulus that small, 10⁵ windows already give about two colliding pairs on average, so pair it with a second, independent hash.

⚠️ Direction matters. This layout gives the outgoing character the highest power, so removing it is a subtraction. If a problem fixes the opposite layout, with the first character multiplied by B⁰, removing it would need a division by B. That is a modular inverse, which may not exist when the modulus is not prime. In that case roll from right to left instead.

Worked example: Repeated DNA Sequences

LeetCode 187: Repeated DNA Sequences asks for every 10-letter sequence that occurs more than once in a DNA string of up to 10⁵ letters from A, C, G, T.

Four letters fit in 2 bits, so ten letters fit in 20 bits. Shift the code left by 2, add the new letter, and mask away everything older than 10 letters:

def find_repeated_dna(s):
    code = {"A": 0, "C": 1, "G": 2, "T": 3}
    mask = (1 << 20) - 1                  # 10 letters x 2 bits
    window = 0
    seen, reported, out = set(), set(), []
    for i, ch in enumerate(s):
        window = ((window << 2) | code[ch]) & mask
        if i >= 9:                        # window now encodes s[i-9 .. i]
            if window in seen and window not in reported:
                reported.add(window)
                out.append(s[i - 9:i + 1])
            seen.add(window)
    return out

On "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT" it returns ['AAAAACCCCC', 'CCCCCAAAAA']. This "hash" is an exact encoding: each 10-letter string maps to its own integer below 2²⁰ = 1,048,576. Equal codes therefore mean equal strings, and the function needs neither a modulus nor a verification step.

💡 Honest accounting. With the window fixed at 10, the plain version, a set of slices s[i:i + 10], is also O(10·n) = O(n) time and O(n) space. In CPython it is even slightly faster: about 0.22 s against 0.26 s for this function on a million letters. Rolling pays off when the window length grows with the input, as in the boss level below.

Prefix hashes: any substring's fingerprint in O(1)

The foundation lesson's prefix sums work for hashes too, with one extra multiplication. Let H[i] be the hash of s[:i]. Then H[r] = H[l]·B^(r−l) + hash(s[l:r]) (mod M), because the first l characters were shifted r − l more places. Solve for the part you want:

def build_prefix_hash(s, B, M):
    H = [0] * (len(s) + 1)         # H[i] = hash of s[:i]
    P = [1] * (len(s) + 1)         # P[i] = B**i % M
    for i, ch in enumerate(s):
        H[i + 1] = (H[i] * B + ord(ch)) % M
        P[i + 1] = P[i] * B % M
    return H, P

def substring_hash(H, P, M, l, r):   # hash of s[l:r]
    return (H[r] - H[l] * P[r - l]) % M

After O(n) preprocessing, you can compare any two substrings in O(1), with the same "equal means probably equal" caveat.

Boss level: Longest Duplicate Substring

LeetCode 1044: Longest Duplicate Substring: return any longest substring that occurs at least twice (occurrences may overlap), or "". The string has up to 3·10⁴ letters. "banana" gives "ana".

Two observations make it tractable:

1. The answer is monotone in the length. If some substring of length L occurs twice, drop the last character of both copies and you have a repeat of length L − 1. So "a repeat of length L exists" is true up to some length and false after it, and you can binary search on L.
2. For a fixed L, roll a hash over every window and group start positions by hash. On a hash hit, compare the actual substrings, so a collision can never produce a wrong answer.

import random

def longest_dup_substring(s):
    MOD = (1 << 61) - 1
    BASE = random.randrange(1 << 20, MOD - 1)
    n = len(s)

    def repeated_start(L):
        """Start of a length-L substring that also occurs earlier, or -1."""
        high = pow(BASE, L - 1, MOD)
        h = 0
        for i in range(L):
            h = (h * BASE + ord(s[i])) % MOD
        buckets = {h: [0]}
        for start in range(1, n - L + 1):
            h = ((h - ord(s[start - 1]) * high) * BASE + ord(s[start + L - 1])) % MOD
            for other in buckets.get(h, []):
                if s[other:other + L] == s[start:start + L]:   # rule out a collision
                    return start
            buckets.setdefault(h, []).append(start)
        return -1

    lo, hi, best = 1, n - 1, ""
    while lo <= hi:
        mid = (lo + hi) // 2
        start = repeated_start(mid)
        if start != -1:
            best, lo = s[start:start + mid], mid + 1    # length mid works: try longer
        else:
            hi = mid - 1                                # mid fails, so does anything longer
    return best

On "banana" the search tries mid = 3 (range 1–5), finds "ana" again at start 3, and moves up. Then it tries mid = 4 (range 4–5), finds no repeat, and the range closes. The answer is "ana".

Cost. There are O(log n) rounds of expected O(n) work each, so O(n log n) expected time and O(n) space. Slicing and hashing every window instead would cost O(n·L) per round, which is O(n² log n) in the worst case.

Your turn: use the digits of "27182", window 3, base 10 and M = 13. The first window gives 271 mod 13 = 11, and the outgoing weight is 100 mod 13 = 9. Roll twice using only the formula. Then say what goes wrong if you port the code to Java unchanged.

Move 3: Grow palindromes from their centres

Smell: the slow code tests every substring separately. That is O(n²) substrings at O(n) per test, so O(n³).

Predict first: how many palindromic substrings does "aaa" have, counting different positions separately? How many possible centres does a string of length n have?

Expand around each centre

A palindrome mirrors around its centre, so its centre and its radius determine it completely. Start at each of the 2n − 1 centres and grow outward while the two ends match. LeetCode 647: Palindromic Substrings counts them, and LeetCode 5: Longest Palindromic Substring returns the longest:

def count_palindromes(s):            # LeetCode 647
    total = 0
    for i in range(len(s)):
        for lo, hi in ((i, i), (i, i + 1)):          # odd centre, even centre
            while lo >= 0 and hi < len(s) and s[lo] == s[hi]:
                total += 1
                lo -= 1
                hi += 1
    return total

def longest_palindrome(s):           # LeetCode 5
    def expand(lo, hi):
        while lo >= 0 and hi < len(s) and s[lo] == s[hi]:
            lo -= 1
            hi += 1
        return lo + 1, hi              # undo the final failed step: s[lo+1:hi]
    best_lo = best_hi = 0
    for i in range(len(s)):
        for lo, hi in (expand(i, i), expand(i, i + 1)):
            if hi - lo > best_hi - best_lo:
                best_lo, best_hi = lo, hi
    return s[best_lo:best_hi]

Trace every centre of "abaab":

count_palindromes("abaab") returns 8, and longest_palindrome("abaab") returns "baab", which comes from a gap. Skip the gaps and you miss it.

Why stopping at the first mismatch is safe

If s[lo] != s[hi], then s[lo..hi] is not a palindrome. Every longer substring with the same centre has s[lo] and s[hi] at mirrored positions too, so none of them is a palindrome either. The palindromes around one centre therefore form an unbroken run of radii, and every palindrome has exactly one centre. The loop counts each one exactly once.

Cost. There are 2n − 1 centres and each expansion takes up to O(n) steps, so the worst case is O(n²) time with O(1) extra space. The string "aaa…a" reaches it, and there the count itself is n(n + 1)/2. LeetCode 5 and 647 allow n ≤ 1,000, so about 10⁶ steps is fine.

Traps

• Forgetting even centres. Code that expands only around characters returns "a" for "abb", where the answer is "bb", and "a" for "abba".
• Off by one after the loop. The loop exits one step too far on each side, so the palindrome is s[lo + 1:hi], not s[lo:hi + 1].
• Slicing to test. Checking s[lo:hi + 1] == s[lo:hi + 1][::-1] at every step makes each step O(n) and the whole thing O(n³).

The DP table, and when it is worth it

The same facts fit in a table: pal[i][j] is true when s[i] == s[j] and the inside s[i+1..j−1] is a palindrome (or is empty or a single character).

def count_palindromes_dp(s):
    n = len(s)
    pal = [[False] * n for _ in range(n)]
    total = 0
    for i in range(n - 1, -1, -1):            # row i+1 is complete before row i starts
        for j in range(i, n):
            pal[i][j] = s[i] == s[j] and (j - i < 2 or pal[i + 1][j - 1])
            total += pal[i][j]
    return total

Fill order. pal[i][j] reads row i + 1, so fill the rows bottom-up, with i running from n − 1 down to 0, or fill by increasing substring length. With for i in range(n), the code reads rows that are still all False: "aaa" gets 5 instead of 6, because "aaa" itself is missed.

The table costs O(n²) time and O(n²) memory, which is worse than expansion for counting. It pays off when a later step asks "is s[i..j] a palindrome?" for many pairs, as palindrome-partitioning problems do. Expansion can serve those problems too: it finds every palindromic (lo, hi) pair in O(n²) total, and you can act on each pair as the loop finds it.

⚠️ Subsequence is a different problem. The longest palindromic subsequence (LeetCode 516) may skip characters, so centres do not apply. Its length equals the longest common subsequence of s and s[::-1], a two-string DP covered in 2D DP & Grid Problems.

Your turn: what is the longest palindrome in "bananas", and how many palindromic substrings does it have? Does an odd or an even centre win?

Boss level: Manacher's algorithm in O(n)

Expansion repeats work: inside a long palindrome, the right half mirrors the left half, so radii already computed on the left predict radii on the right. Manacher's algorithm uses that in two steps.

Step 1: one kind of centre. Put a separator between all characters and at both ends: "abaa" becomes "#a#b#a#a#". Now every palindrome has odd length and a single middle index, and a centre on a # stands for an even-length palindrome of the original. The radius p[i] (characters on each side) in the new string t equals the length of the matching palindrome in s:

p[3] = 3 is "aba". p[6] = 2 is "aa", centred between the last two as. The largest radius, 3, is the longest palindrome's length, and the sum of (p[i] + 1) // 2 over all i, which is 6, is the number of palindromic substrings of "abaa".

Step 2: borrow from the mirror. Remember the palindrome that reaches furthest right, with centre center and right edge right. For i < right, its mirror is j = 2·center − i. Inside the big palindrome, the neighbourhood of i is a reflection of the neighbourhood of j, so p[i] ≥ min(p[j], right − i). The cap matters, because beyond right nothing is known. In "abab" → "#a#b#a#b#", the palindrome centred at 5 reaches right = 8. At i = 7 the mirror is 3, with p[3] = 3, but only right − i = 1 is guaranteed. An uncapped p[7] = 3 would claim a palindrome that runs past the end of the string; the true radius is 1.

def manacher(s):
    t = "#" + "#".join(s) + "#"      # "abaa" -> "#a#b#a#a#"
    p = [0] * len(t)                 # p[i] = radius of the palindrome centred at t[i]
    center = right = 0               # t[2*center-right .. right] is the rightmost palindrome
    for i in range(len(t)):
        if i < right:
            p[i] = min(p[2 * center - i], right - i)   # mirror, capped at the known boundary
        while (i - p[i] - 1 >= 0 and i + p[i] + 1 < len(t)
               and t[i - p[i] - 1] == t[i + p[i] + 1]):
            p[i] += 1
        if i + p[i] > right:
            center, right = i, i + p[i]
    return p

Why it is linear. When the mirrored value lies strictly inside the big palindrome, the expansion fails on its first comparison. Otherwise the expansion starts at right, so every successful comparison pushes right one step further. right never exceeds len(t) = 2n + 1, so the total is O(n) time and O(n) space. The separator never causes trouble either: the two positions compared, i − r and i + r, always have the same parity, so a separator is only ever compared with another separator. Any symbol works, even one that occurs in s.

When to reach for it. You need Manacher when n is large and you need the radius at every centre. On 10⁵ copies of a, expansion makes n(n + 1)/2 ≈ 5·10⁹ successful steps. For LeetCode 5 and 647, with n ≤ 1,000, expansion is simpler and fast enough. The rightmost-box trick is the same one the Z-function uses.

String hygiene: bugs that are not algorithmic

A correct algorithm still fails if the characters are not what you assumed.

The alphabet decides the container. "Lowercase English letters" allows a 26-slot count array, as in the foundation lesson. Unicode has 1,114,112 code points (U+0000 to U+10FFFF), and more than 150,000 of them are encoded characters, a number that grows with each Unicode version. For arbitrary text, count with a dictionary of the characters you actually meet: O(min(n, σ)) space.

ASCII arithmetic. 'A' is 65 and 'a' is 97. They differ by 32, a single bit, so chr(ord(c) ^ 32) flips the case of an ASCII letter. It garbles anything that is not an ASCII letter. 'a' ^ 32 itself is a TypeError in Python, because a str is not an integer.

What len counts. Python counts code points: len("😀") is 1, although the emoji takes 4 bytes in UTF-8. Java's String.length() and JavaScript's .length count UTF-16 units and return 2, so index arithmetic ported between languages can break on emoji. A visible é can also be one code point (U+00E9) or two (e followed by the combining accent U+0301). The two forms print identically, compare unequal and have different lengths. Normalize first with unicodedata.normalize("NFC", s).

Case. lower() is fine for English. For caseless comparison use casefold(): "straße".lower() stays "straße", while casefold() gives "strasse", which matches "STRASSE".casefold(). casefold() ignores locale: it maps "I" to "i", which is wrong for Turkish, where the lowercase of I is the dotless ı. Locale-aware comparison needs a library.

Whitespace. " hello world ".split(' ') gives ['', '', 'hello', '', 'world', '', ''], with one empty string per extra space. split() with no argument splits on runs of whitespace and gives ['hello', 'world'].

Edge cases to try before you submit:

• the empty text, the empty pattern ("abc".find("") is 0), and a pattern longer than the text
• a single character, and all characters equal: "aaaa" is the worst case for naive search, for expansion and for hash verification
• overlapping matches (count versus kmp_find_all)
• the last window, which starts at n − m, so loop over range(n - m + 1)
• a separator character that might also occur in the input

Your turn: predict all six printed values.

import unicodedata

a = "caf\u00e9"         # é as one code point
b = "cafe\u0301"        # e + combining acute accent
print(a == b, len(a), len(b))
print(unicodedata.normalize("NFC", a) == unicodedata.normalize("NFC", b))
print("STRASSE".lower() == "straße".lower(), "STRASSE".casefold() == "straße".casefold())

False 4 5
True
False True

Which string tool? A routing table

Final round: no label on the problem

Real problems don't say which move they want. Decide what is really being asked, then pick the tool.

Challenge 1: is it a rotation?

LeetCode 796: Rotate String: can s become goal by repeatedly moving its first character to the end? s = "abcde", goal = "cdeab" gives True; goal = "abced" gives False.

1. Which move applies, and why?
2. What check must come before the search?
3. What does it cost?

def rotate_string(s, goal):
    return len(s) == len(goal) and kmp_find(s + s, goal) != -1

Challenge 2: made of one repeated block?

LeetCode 459: Repeated Substring Pattern: can s be built by writing some shorter substring several times? "abab" gives True, "aba" gives False, and "abcabcabcabc" gives True. The input has up to 10⁴ characters.

def repeated_substring_pattern(s):
    pi_last = prefix_function(s)[-1]
    period = len(s) - pi_last
    return pi_last > 0 and len(s) % period == 0

Challenge 3: Shortest Palindrome

LeetCode 214: Shortest Palindrome: add as few characters as possible to the front of s to make it a palindrome. "aacecaaa" gives "aaacecaaa", and "abcd" gives "dcbabcd". The input has up to 5·10⁴ characters.

1. What is the question really asking?
2. Which move answers it in O(n)?

def shortest_palindrome(s):
    rev = s[::-1]
    k = prefix_function(s + "#" + rev)[-1]   # longest palindromic prefix of s
    return rev[:len(s) - k] + s

Challenge 4: anagram positions

LeetCode 438: Find All Anagrams in a String: return every start index where a rearrangement of p occurs in s. s = "cbaebabacd", p = "abc" gives [0, 6]. Both strings have up to 3·10⁴ lowercase letters. Does KMP or a rolling hash of p help?

def find_anagrams(s, p):
    m = len(p)
    if m > len(s):
        return []
    need, have = [0] * 26, [0] * 26
    for ch in p:
        need[ord(ch) - ord("a")] += 1
    hits = []
    for i, ch in enumerate(s):
        have[ord(ch) - ord("a")] += 1
        if i >= m:
            have[ord(s[i - m]) - ord("a")] -= 1   # the letter leaving the window
        if i >= m - 1 and have == need:
            hits.append(i - m + 1)
    return hits

Cheat sheet: smell → move

Before moving on, take one problem from this lesson and explain it from a blank editor: what the slow version repeats, what pi, h or p means at a given moment in the loop, why the fast version skips nothing, what it costs and why, and which input would break a small change to it (a reset instead of a fallback, a missing verification, a forgotten even centre).

Next: String Algorithms is the last topic of this roadmap. To go further with strings, revisit Sliding Window Patterns for constrained substrings, Trees & Advanced Structures for tries, and 2D DP & Grid Problems for edit distance and LCS.