DevPath
Tracks

String Algorithms

Anagram checks with counts, linear-time pattern matching with KMP and rolling hashes, and palindromes by expanding around centers.

intermediate45 min#strings#kmp#rolling-hash#palindromes#anagrams

Prerequisites: Arrays and Dynamic Arrays, Hash Tables

Why it matters

Text is everywhere: search boxes, log files, DNA, source code, URLs. Searching for a pattern inside text, comparing words, and finding symmetric structure are daily tasks, and the naive approaches get slow on large inputs. String problems are also among the most frequent interview questions, and most reduce to a handful of ideas: count characters, slide a window, reuse what you already matched, or expand from a center.

Intuition

Counting. Two words are anagrams if they contain the same letters the same number of times. Order does not matter, so a tally of letters is a complete fingerprint.

Reusing matches (KMP). Searching for "abab" in "abababab", a naive search that fails at the fifth character starts over one position later and re-reads letters it has already seen. But you already know that the last two letters matched the first two letters of the pattern ("ab"), so you can resume with those two matched and not re-read anything. KMP precomputes that knowledge from the pattern alone.

Expanding from a center. A palindrome mirrors around its middle. Pick a middle and grow outward while both sides match. There are 2n - 1 middles (each character, and each gap between two characters).

How it works

Anagrams. Build a count map for each string and compare, or increment counts for one string and decrement for the other and check that nothing goes negative. O(n) time, O(alphabet) space. To find all anagrams of a word inside a longer text, slide a fixed window and update counts incrementally.

Here is that fixed window sliding over cbabca, looking for anagrams of abc.

c
0
b
1
a
2
b
3
c
4
a
5
Find every anagram of abc (counts a:1, b:1, c:1) in cbabca. The window is 3 wide.
step 1 / 5

The count map is updated in O(1) per slide (one letter out, one letter in), so scanning the whole text is O(n). Green windows are anagrams, amber windows are not.

Naive search tries each start and compares up to m characters: O(n * m) worst case, like searching for "aaab" in "aaaa...a".

KMP builds a prefix table for the pattern: table[i] is the length of the longest proper prefix of p[0..i] that is also a suffix of it. For "ababaca" the table is 0 0 1 2 3 0 1. During search, when a mismatch happens after k matched characters, fall back to table[k - 1] instead of restarting. The text index never moves backwards, and k can only fall as far as it has risen, so the total work is O(n + m).

Here is the table for ababaca being built, one position at a time.

0123456
pattern
a
b
a
b
a
c
a
table
0
Pattern ababaca. table[i] is the longest proper prefix of p[0..i] that is also a suffix of it. A single letter has no proper prefix, so table[0] = 0. k tracks the current match length, starting at 0.
step 1 / 7

Green is the character being added, amber is the pattern character it is compared with. At i = 5 the fall back chain k = 3, 1, 0 shows how the table lets KMP skip re-reading text.

text:    a b a b a b a b
pattern: a b a b            match at 0
              a b a b       match at 2  (fell back to k = 2, not 0)
                    a b a b match at 4

The same search, step by step, with i as the text index and k as the matched length.

a
0
i
b
1
a
2
b
3
a
4
b
5
a
6
b
7
Search abab in abababab with table 0 0 1 2. k is how many pattern letters are matched. Start at i = 0, k = 0.
step 1 / 6

The text index i never moves back. After each full match the pattern restarts with the overlap (k = 2) already counted, which is how the three overlapping matches are found with one pass.

Rolling hash (Rabin-Karp) compares a numeric fingerprint of each text window to the pattern's fingerprint. Because the hash of the next window can be computed from the previous one in O(1) (subtract the outgoing character, shift, add the incoming one), scanning is O(n) on average. Equal hashes can be collisions, so confirm candidates with a direct comparison. Its strength is multi-pattern search and problems like finding repeated substrings with binary search.

Palindromes. Expanding around each of the 2n - 1 centers costs O(n) per center in the worst case, so O(n^2) total with O(1) space. This is the practical interview answer. A dynamic programming table is also O(n^2) but uses O(n^2) memory, and Manacher's algorithm gets O(n) with more effort.

Here is expand-around-center on xabbay, which has both an odd and an even center worth trying.

x
0
a
1
b
2
b
3
a
4
y
5
Find the longest palindrome in xabbay by expanding from each of the 2n - 1 = 11 centers. Pick a center, then grow outward while both ends match.
step 1 / 6

Green is the palindrome found so far, amber is the pair that failed to match. Even-length palindromes need a center between two characters, which is why there are 2n - 1 centers, not n.

OperationTimeNotes
Anagram check (count map)O(n)O(alphabet) extra space
Naive substring searchO(n * m)Worst case, repeated characters
KMP searchO(n + m)Prefix table costs O(m)
Rabin-KarpO(n + m) averageO(n * m) if many collisions
Longest palindrome, expand around centerO(n^2)O(1) extra space

Code: anagrams, KMP, palindromes

from collections import Counter
 
def is_anagram(a, b):
    return Counter(a) == Counter(b)
 
def prefix_table(p):
    """table[i] = length of the longest proper prefix of p[:i+1] that is also its suffix."""
    table = [0] * len(p)
    k = 0
    for i in range(1, len(p)):
        while k > 0 and p[i] != p[k]:
            k = table[k - 1]
        if p[i] == p[k]:
            k += 1
        table[i] = k
    return table
 
def kmp_search(text, p):
    table, k, hits = prefix_table(p), 0, []
    for i, ch in enumerate(text):
        while k > 0 and ch != p[k]:
            k = table[k - 1]         # fall back, never move i backwards
        if ch == p[k]:
            k += 1
        if k == len(p):
            hits.append(i - k + 1)
            k = table[k - 1]
    return hits
 
def longest_palindrome(s):
    best = ""
    for center in range(2 * len(s) - 1):
        l, r = center // 2, center // 2 + center % 2
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1
            r += 1
        if r - l - 1 > len(best):
            best = s[l + 1:r]
    return best
 
print(str(is_anagram("listen", "silent")).lower(), str(is_anagram("rat", "car")).lower())
print(*prefix_table("ababaca"))
print(*kmp_search("abababab", "abab"))
print(longest_palindrome("forgeeksskeegfor"))

Both versions print four lines: true false (listen and silent are anagrams; rat and car are not), 0 0 1 2 3 0 1 (the prefix table of "ababaca"), 0 2 4 (match positions of "abab" in "abababab", overlaps included), and geeksskeeg (the longest palindrome in "forgeeksskeegfor").

Common pitfalls

  • Ignoring case, spaces, and Unicode: decide whether "Listen" equals "silent". With non-ASCII text, one visible character can be several code points, so counting needs normalization first.
  • Strings are immutable: repeatedly doing s = s + ch or slicing in a loop can silently become O(n^2). Build a list and join once, or track indexes.
  • Off-by-one in the prefix table: the fallback is table[k - 1], not table[k]. After a full match, also fall back so overlapping matches are found.
  • Hash collisions: Rabin-Karp with equal hashes is only a candidate. Verify before reporting a match.
  • Forgetting even-length palindromes: centering only on characters misses "abba". Use both a character and a gap as centers.

Practice

Valid palindrome easy

Hint

Two pointers from both ends. Skip anything that is not a letter or digit.

Show solution

Move l right and r left past non-alphanumeric characters, compare the lowercase characters, and return false on any mismatch. O(n) time, O(1) space.

Find all anagrams in a string medium

Hint

Fixed-size sliding window of the pattern's length, with a count map you update as it slides.

Show solution

Count the letters of the pattern. Slide a window of the same length over the text, adding the entering letter and removing the leaving one. Whenever the window counts equal the pattern counts, record the start index. Compare counts in O(alphabet), so the total is O(n * alphabet), effectively O(n).

Repeated substring pattern medium

Hint

Look at the KMP prefix table of the whole string. What does the last entry tell you about the period?

Show solution

Compute the prefix table. Let L = len(s) and p = table[L - 1]. The string is built from a repeated block exactly when p > 0 and L % (L - p) == 0. The block length is L - p. O(L).

Longest palindromic substring in linear time hard

Hint

Reuse the mirror of an already known palindrome so you never re-compare matched characters, the same spirit as KMP.

Show solution

Manacher's algorithm transforms the string by inserting separators, then keeps the rightmost palindrome seen (center and right edge). For a new center inside that palindrome, its radius starts at the mirrored center's radius (capped by the edge) and expands only beyond the edge. Every expansion moves the right edge forward, giving O(n) total. In an interview, state the idea and deliver expand-around-center unless asked.

Interview questions

  1. How would you check if two strings are anagrams? Compare letter counts in O(n) with a map or fixed-size array. Sorting both also works in O(n log n) and is simpler.
  2. Why is KMP linear? The text pointer never goes back, and the matched length k rises by at most one per character, so the total fallbacks cannot exceed the total increments.
  3. What is a rolling hash and what is its risk? A hash of a window that updates in O(1) when the window slides. The risk is collisions, so a match must be verified.
  4. Time complexity of longest palindromic substring by expanding around centers? O(n^2) time, O(1) space.

Interviewers look for: asking about case and character set, naming the naive cost before improving it, and handling both odd and even palindromes.

Quick check

In KMP, what does table[i] store?

Finished this lesson?

Further resources

Related lessons