Tries and String Algorithms

String problems appear in almost every interview loop. Many are solved by ideas from earlier chapters (hash maps, two pointers, sliding windows, dynamic programming). This chapter adds the structures and algorithms that are specific to strings: the trie for prefix queries, KMP and rolling hashes for pattern matching, and a toolbox of string manipulation techniques. It closes with the common traps of working with strings in Python.

1. Strings in Python: costs and idioms

Strings are immutable. Every "modification" creates a new string, so repeated concatenation in a loop is quadratic.

parts = []
for ch in "hello":
    parts.append(ch.upper())          # collect pieces
result = "".join(parts)               # one O(n) join at the end
assert result == "HELLO"

s = "interview"
assert s[2:5] == "ter" and s[::-1] == "weivretni"     # slicing copies, O(k)
assert "view" in s and s.find("view") == 5 and s.find("zzz") == -1
assert s.startswith("inter") and s.count("e") == 2
assert ord("a") == 97 and chr(98) == "b" and ord("c") - ord("a") == 2

Useful facts: comparing two strings is $O(\min (\text{len}))$. str.split, join, strip, isalnum, isdigit, lower exist, and collections.Counter gives character frequencies. For character counts over a lowercase alphabet, a list of 26 integers is both faster and hashable when converted to a tuple.

2. The trie

A trie (prefix tree) stores a set of strings so that strings sharing a prefix share a path. Each node represents a prefix, with one child per next character and a flag marking where a whole word ends. Insertion and lookup take time proportional to the length of the word, not the number of words, and prefix queries are natural.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_word = True

    def _walk(self, prefix):
        node = self.root
        for ch in prefix:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

    def search(self, word):
        node = self._walk(word)
        return node is not None and node.is_word

    def starts_with(self, prefix):
        return self._walk(prefix) is not None

t = Trie()
for w in ["apple", "app", "apt", "bat"]:
    t.insert(w)
assert t.search("app") and not t.search("ap")
assert t.starts_with("ap") and not t.starts_with("c")

Time $O(L)$ per operation for a word of length $L$. Space up to $O(\text{total characters})$ in the worst case, with sharing reducing it. A dictionary of children is flexible for any alphabet. An array of 26 children is faster for lowercase letters but uses more memory per node.

When to use a trie instead of a hash set: prefix queries (autocomplete, "does any word start with this"), searching many words at once in a grid, longest common prefix, and replacing words by their roots. A hash set answers "is this exact word present" in $O(L)$ as well, so a trie is justified only when you need prefix behaviour.

Autocomplete. Walk to the prefix node, then collect all words below it.

def autocomplete(trie, prefix, limit=10):
    node = trie._walk(prefix)
    results = []
    def collect(n, path):
        if len(results) >= limit:
            return
        if n.is_word:
            results.append(prefix + path)
        for ch in sorted(n.children):
            collect(n.children[ch], path + ch)
    if node:
        collect(node, "")
    return results

assert autocomplete(t, "ap") == ["app", "apple", "apt"]
assert autocomplete(t, "z") == []

Word search II. Find all words from a list that exist in a grid. Doing the backtracking search of the previous chapter once per word is slow. Insert all words into a trie, then run one DFS from each cell, following trie edges: if the current path is not a prefix of any word, stop immediately.

def find_words(board, words):
    root = TrieNode()
    for w in words:
        node = root
        for ch in w:
            node = node.children.setdefault(ch, TrieNode())
        node.is_word = w                                  # store the word itself at its end node
    rows, cols = len(board), len(board[0])
    found = set()
    def dfs(r, c, node):
        ch = board[r][c]
        nxt = node.children.get(ch)
        if nxt is None:
            return                                        # no word has this prefix: prune
        if nxt.is_word:
            found.add(nxt.is_word)
        board[r][c] = "#"
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != "#":
                dfs(nr, nc, nxt)
        board[r][c] = ch
    for r in range(rows):
        for c in range(cols):
            dfs(r, c, root)
    return sorted(found)

b = [list("oaan"), list("etae"), list("ihkr"), list("iflv")]
assert find_words(b, ["oath", "pea", "eat", "rain"]) == ["eat", "oath"]

Longest common prefix of a list of words: walk the trie while the node has exactly one child and is not a word end. Or simply compare column by column, which is simpler and what most candidates write.

def longest_common_prefix(strs):
    if not strs:
        return ""
    prefix = strs[0]
    for s in strs[1:]:
        while not s.startswith(prefix):
            prefix = prefix[:-1]
            if not prefix:
                return ""
    return prefix

assert longest_common_prefix(["flower", "flow", "flight"]) == "fl"
assert longest_common_prefix(["dog", "racecar", "car"]) == ""

3. Substring search

Find the first occurrence of pattern in text.

Brute force compares at every position, $O(nm)$ in the worst case. In practice, Python's in and find are fast, and for an interview you should be able to explain how to do better.

KMP (Knuth-Morris-Pratt) avoids re-examining text characters by precomputing, for each prefix of the pattern, the length of the longest proper prefix that is also a suffix (the failure function). When a mismatch occurs, instead of restarting, it shifts the pattern using that table. Total time is $O(n+m)$.

def build_lps(pattern):
    lps = [0] * len(pattern)                 # lps[i] = length of the longest border of pattern[:i+1]
    length = 0
    for i in range(1, len(pattern)):
        while length and pattern[i] != pattern[length]:
            length = lps[length - 1]         # fall back to a shorter border
        if pattern[i] == pattern[length]:
            length += 1
        lps[i] = length
    return lps

def kmp_search(text, pattern):
    if not pattern:
        return 0
    lps = build_lps(pattern)
    j = 0
    for i, ch in enumerate(text):
        while j and ch != pattern[j]:
            j = lps[j - 1]                   # shift the pattern, never move back in the text
        if ch == pattern[j]:
            j += 1
        if j == len(pattern):
            return i - len(pattern) + 1
    return -1

assert build_lps("ababaca") == [0, 0, 1, 2, 3, 0, 1]
assert kmp_search("sadbutsad", "sad") == 0
assert kmp_search("leetcode", "leeto") == -1
assert kmp_search("mississippi", "issip") == 4

The key idea to state: the text pointer never moves backward, because the failure table tells us how much of the pattern is still known to match.

Rolling hash (Rabin-Karp). Compute a hash of each window of the text in $O(1)$ from the previous window's hash, comparing it with the pattern's hash, and verify on a match. It extends naturally to finding repeated substrings and to multiple patterns.

def rabin_karp(text, pattern, base=256, mod=1_000_000_007):
    n, m = len(text), len(pattern)
    if m > n:
        return -1
    high = pow(base, m - 1, mod)                     # weight of the leading character
    p_hash = t_hash = 0
    for i in range(m):
        p_hash = (p_hash * base + ord(pattern[i])) % mod
        t_hash = (t_hash * base + ord(text[i])) % mod
    for i in range(n - m + 1):
        if p_hash == t_hash and text[i:i + m] == pattern:      # verify to rule out collisions
            return i
        if i < n - m:
            t_hash = ((t_hash - ord(text[i]) * high) * base + ord(text[i + m])) % mod
    return -1

assert rabin_karp("sadbutsad", "sad") == 0
assert rabin_karp("abcdef", "def") == 3
assert rabin_karp("abc", "abcd") == -1

Expected time $O(n+m)$, with $O(nm)$ possible in the worst case if many collisions force verification. Use a large modulus (and sometimes two) to make collisions rare.

4. Palindromes and symmetry

Expand around centre finds palindromic substrings in $O(n^2)$. Count palindromic substrings:

def count_palindromic_substrings(s):
    count = 0
    for centre in range(2 * len(s) - 1):              # 2n-1 centres: characters and gaps
        left = centre // 2
        right = left + centre % 2
        while left >= 0 and right < len(s) and s[left] == s[right]:
            count += 1
            left -= 1
            right += 1
    return count

assert count_palindromic_substrings("abc") == 3
assert count_palindromic_substrings("aaa") == 6

Valid palindrome after deleting at most one character. Use two pointers, and on the first mismatch try skipping either side.

def valid_palindrome_ii(s):
    def is_pal(lo, hi):
        while lo < hi:
            if s[lo] != s[hi]:
                return False
            lo += 1; hi -= 1
        return True
    lo, hi = 0, len(s) - 1
    while lo < hi:
        if s[lo] != s[hi]:
            return is_pal(lo + 1, hi) or is_pal(lo, hi - 1)
        lo += 1; hi -= 1
    return True

assert valid_palindrome_ii("aba") is True
assert valid_palindrome_ii("abca") is True
assert valid_palindrome_ii("abc") is False

5. Anagrams and character counting

Two strings are anagrams if they have the same character counts. A fixed sliding window over a longer string, maintaining counts, finds all anagram positions in $O(n)$.

from collections import Counter

def find_anagrams(s, p):
    need, window = Counter(p), Counter()
    result, k = [], len(p)
    for i, ch in enumerate(s):
        window[ch] += 1
        if i >= k:
            left = s[i - k]
            window[left] -= 1
            if window[left] == 0:
                del window[left]                      # keep the Counters comparable
        if window == need:
            result.append(i - k + 1)
    return result

assert find_anagrams("cbaebabacd", "abc") == [0, 6]
assert find_anagrams("abab", "ab") == [0, 1, 2]

Valid anagram is one line with Counter. Group anagrams uses a canonical key (see the arrays chapter). Permutation in string is the same sliding-window idea.

6. String parsing and simulation

Interviews also test careful implementation. Write the edge cases first.

String to integer (atoi). Skip whitespace, read an optional sign, read digits, clamp to the 32-bit range.

def my_atoi(s):
    s = s.lstrip()
    if not s:
        return 0
    sign, i = 1, 0
    if s[0] in "+-":
        sign = -1 if s[0] == "-" else 1
        i = 1
    value = 0
    while i < len(s) and s[i].isdigit():
        value = value * 10 + int(s[i])
        i += 1
    value *= sign
    return max(-2**31, min(2**31 - 1, value))

assert my_atoi("42") == 42
assert my_atoi("   -42") == -42
assert my_atoi("4193 with words") == 4193
assert my_atoi("words 987") == 0
assert my_atoi("-91283472332") == -2**31

Add binary / add strings processes digits from the right with a carry. Roman to integer adds values, subtracting when a smaller value precedes a larger one.

def roman_to_int(s):
    values = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
    total = 0
    for i, ch in enumerate(s):
        if i + 1 < len(s) and values[ch] < values[s[i + 1]]:
            total -= values[ch]
        else:
            total += values[ch]
    return total

assert roman_to_int("III") == 3
assert roman_to_int("LVIII") == 58
assert roman_to_int("MCMXCIV") == 1994

def add_binary(a, b):
    i, j, carry, out = len(a) - 1, len(b) - 1, 0, []
    while i >= 0 or j >= 0 or carry:
        total = carry + (int(a[i]) if i >= 0 else 0) + (int(b[j]) if j >= 0 else 0)
        out.append(str(total % 2))
        carry = total // 2
        i -= 1; j -= 1
    return "".join(reversed(out))

assert add_binary("11", "1") == "100"
assert add_binary("1010", "1011") == "10101"

Run-length encoding and compression, reverse words in a string, longest common prefix and zigzag conversion test patience and boundaries more than algorithms. Write helper functions and test with empty strings, single characters and repeated patterns.

7. Choosing among the techniques

8. Common mistakes

• Building strings with += in a loop for large outputs. Use a list and join.
• Slicing inside loops, making an $O(n)$ operation hidden in each iteration.
• Assuming ASCII or lowercase only. Ask about the character set.
• Index errors on empty or one-character strings.
• Forgetting that strings are immutable, so in-place reversal needs a list of characters.
• Not verifying a hash match, so a collision gives a wrong answer.
• Trie memory blowup with a 26-entry array per node when the data is sparse. A dictionary can use less.
• Comparing counters with zero entries. In older Python versions, a Counter holding an explicit zero count does not compare equal to one without the key, so delete zero entries as in the anagram code above.
• Case sensitivity and Unicode in palindrome and anagram problems. Clarify.

9. Practice set

1. Implement trie, add and search words (with . wildcard), design a search autocomplete system.
2. Word search II, replace words, longest word in a dictionary.
3. Find the index of the first occurrence (KMP), repeated substring pattern, shortest palindrome.
4. Longest palindromic substring, palindromic substrings, valid palindrome II.
5. Valid anagram, group anagrams, find all anagrams, permutation in string.
6. Longest substring without repeating characters, minimum window substring.
7. String to integer, add strings, multiply strings, roman to integer, integer to roman.
8. Reverse words in a string, zigzag conversion, text justification.
9. Longest repeating substring (binary search with a rolling hash), longest duplicate substring.
10. Decode string, basic calculator, simplify path.