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.
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.
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.
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.
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.
| Operation | Time | Notes |
|---|---|---|
| Anagram check (count map) | O(n) | O(alphabet) extra space |
| Naive substring search | O(n * m) | Worst case, repeated characters |
| KMP search | O(n + m) | Prefix table costs O(m) |
| Rabin-Karp | O(n + m) average | O(n * m) if many collisions |
| Longest palindrome, expand around center | O(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"))function isAnagram(a, b) {
if (a.length !== b.length) return false;
const counts = new Map();
for (const ch of a) counts.set(ch, (counts.get(ch) ?? 0) + 1);
for (const ch of b) {
if (!counts.get(ch)) return false;
counts.set(ch, counts.get(ch) - 1);
}
return true;
}
// table[i] = length of the longest proper prefix of p[0..i] that is also its suffix.
function prefixTable(p) {
const table = new Array(p.length).fill(0);
let k = 0;
for (let i = 1; i < p.length; i++) {
while (k > 0 && p[i] !== p[k]) k = table[k - 1];
if (p[i] === p[k]) k++;
table[i] = k;
}
return table;
}
function kmpSearch(text, p) {
const table = prefixTable(p), hits = [];
let k = 0;
for (let i = 0; i < text.length; i++) {
while (k > 0 && text[i] !== p[k]) k = table[k - 1]; // fall back, never move i backwards
if (text[i] === p[k]) k++;
if (k === p.length) {
hits.push(i - k + 1);
k = table[k - 1];
}
}
return hits;
}
function longestPalindrome(s) {
let best = "";
for (let center = 0; center < 2 * s.length - 1; center++) {
let l = Math.floor(center / 2), r = l + (center % 2);
while (l >= 0 && r < s.length && s[l] === s[r]) {
l--;
r++;
}
if (r - l - 1 > best.length) best = s.slice(l + 1, r);
}
return best;
}
console.log(isAnagram("listen", "silent"), isAnagram("rat", "car"));
console.log(...prefixTable("ababaca"));
console.log(...kmpSearch("abababab", "abab"));
console.log(longestPalindrome("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 + chor 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], nottable[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
- 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.
- Why is KMP linear? The text pointer never goes back, and the matched length
krises by at most one per character, so the total fallbacks cannot exceed the total increments. - 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.
- 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
- Knuth-Morris-Pratt algorithm (Wikipedia) (article)
- Rabin-Karp algorithm (Wikipedia) (article)
- Longest palindromic substring (Wikipedia) (article)
- Python docs: collections (docs)