Strings and tries cheat sheet

How many words start with a given prefix?

A trie stores words letter by letter in a tree; words sharing a start share a path. Store at each node how many words pass through it. Building costs O(total letters); each prefix question walks at most its own length, O(p), and reads the count at the last node. With T total letters that is O(T + p) time and O(T) space.

Longest stretch that reads the same backwards

Every such stretch has a centre: a letter (odd length) or the gap between two letters (even length). For each of the 2n - 1 centres, expand outward while the ends match, and keep the longest. O(n²) time and O(1) extra memory, with simple code.

def longest_mirror(text: str) -> str:
    best_start, best_len = 0, 0
    for centre in range(2 * len(text) - 1):  # letters and gaps
        lo, hi = centre // 2, centre // 2 + centre % 2
        while 0 <= lo and hi < len(text) and text[lo] == text[hi]:
            lo, hi = lo - 1, hi + 1
        size = hi - lo - 1  # the last pair that matched
        if size > best_len:
            best_start, best_len = lo + 1, size
    return text[best_start:best_start + best_len]

First place a pattern appears in a text

Precompute, for each prefix of the pattern, the longest proper prefix that is also a suffix (its border). While scanning the text, on a mismatch fall back to the border instead of restarting, so text letters are never re-read. Both phases are linear: O(n + m) time, O(m) memory. This is the Knuth-Morris-Pratt algorithm.

Top three suggestions as you type

Sort the words once. For each prefix, binary search the first word that is not smaller than the prefix; matching words follow it contiguously, so check the next three. Sorting costs O(n log n · L) and each prefix O(log n · L). For m typed letters the whole job is O((n + m) log n · L) time, with O(n) space for the sorted copy. A trie storing the top three at each node answers each prefix in O(1) after the build.

from bisect import bisect_left


def suggest(words: list[str], typed: str) -> list[list[str]]:
    ordered = sorted(words)
    out: list[list[str]] = []
    for end in range(1, len(typed) + 1):
        prefix = typed[:end]
        first = bisect_left(ordered, prefix)  # matches start here
        window = ordered[first:first + 3]
        picks = [w for w in window if w.startswith(prefix)]
        out.append(picks)
    return out

Look up words where '.' stands for any letter

Store the words in a trie with an end marker. A query walks the trie letter by letter; at a '.', try every child. Plain letters cost O(1) per step; each '.' can branch, so the worst case is the number of trie nodes, but typical queries are fast. Building is O(total letters). With T total letters and q ≥ 1 queries the worst case is O(q · T) time, and the trie takes O(T) space.

Count the stretches that read the same backwards

Expand around each of the 2n - 1 centres, adding one for every step where the ends still match. Every qualifying substring has exactly one centre, so each is counted once. O(n²) time, O(1) memory.

def count_mirrors(text: str) -> int:
    total = 0
    for centre in range(2 * len(text) - 1):  # letters and gaps
        lo, hi = centre // 2, centre // 2 + centre % 2
        while 0 <= lo and hi < len(text) and text[lo] == text[hi]:
            total += 1  # text[lo:hi + 1] reads the same backwards
            lo, hi = lo - 1, hi + 1
    return total

Longest start shared by every word

Compare column by column: for position i, check that every word has a letter there and that it matches the first word's. Stop at the first mismatch. O(S) time for S total letters in the worst case, O(1) extra memory. Comparing only the smallest and largest word in sorted order also works, since they differ the most.

def shared_start(words: list[str]) -> str:
    if not words:
        return ""
    first = words[0]
    for i, ch in enumerate(first):
        for w in words[1:]:
            if i == len(w) or w[i] != ch:  # this column disagrees
                return first[:i]
    return first

What Python string operations cost

Strings are immutable: slicing s[i:j] copies j - i characters, s + t builds a new string, and s += c in a loop can cost O(n²) in general (CPython sometimes optimises it, but do not rely on it). Indexing and len() are O(1). Build with a list and "".join(), and pass indexes instead of slices into recursive helpers.

Trie or hash set?

A set answers 'is this exact word stored?' in O(L) (hashing the word) with less memory. A trie also answers prefix questions: how many words start with p, list them, autocomplete, wildcard lookups, and the longest stored prefix of a query, all in time proportional to the prefix. Pick a set for exact membership only; a trie when prefixes matter.

Rolling hashes for pattern search

Treat each window of m characters as a number in some base, modulo a large prime. Moving the window one step removes the leading character's contribution and adds the new one in O(1), so all window hashes cost O(n). When a window's hash equals the pattern's, compare the characters to rule out a collision. Expected O(n + m); worst case O(n × m) if many collisions.