Why String Algorithms Matter in Interviews
String problems are ubiquitous in technical interviews at Google, Meta, Amazon, and Microsoft. Key patterns: sliding window for substring problems, two pointers for palindrome and reversal, hashing for anagram detection, and KMP/Rabin-Karp for pattern matching. Recognizing the right pattern for a string problem is the skill that distinguishes candidates who struggle with O(n²) solutions from those who solve in O(n).
Pattern 1: Sliding Window for Substrings
Use a sliding window when the problem asks for “the longest/shortest substring with property X.” Expand right, contract left when the property is violated.
def longest_substring_without_repeat(s):
char_index = {}
left = max_len = 0
for right, c in enumerate(s):
if c in char_index and char_index[c] >= left:
left = char_index[c] + 1 # shrink window
char_index[c] = right
max_len = max(max_len, right - left + 1)
return max_len
# LeetCode 3 — O(n) time, O(k) space where k = charset size
def min_window_substring(s, t):
need = Counter(t)
have, total = 0, len(need)
window = {}
left = best = best_l = 0
best_r = float('inf')
for right, c in enumerate(s):
window[c] = window.get(c, 0) + 1
if c in need and window[c] == need[c]:
have += 1
while have == total:
if right - left < best_r - best_l:
best_l, best_r = left, right
window[s[left]] -= 1
if s[left] in need and window[s[left]] < need[s[left]]:
have -= 1
left += 1
return s[best_l:best_r+1] if best_r != float('inf') else ''
# LeetCode 76 — O(|s| + |t|)
Pattern 2: Two Pointers for Palindromes
def longest_palindrome(s):
def expand(l, r):
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1; r += 1
return s[l+1:r]
result = ''
for i in range(len(s)):
odd = expand(i, i) # odd-length palindrome
even = expand(i, i+1) # even-length palindrome
result = max(result, odd, even, key=len)
return result
# LeetCode 5 — O(n²) but optimal for this problem formulation
def is_palindrome(s):
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
return False
left += 1; right -= 1
return True
Pattern 3: Hashing for Anagrams
from collections import Counter
def find_all_anagrams(s, p):
# Sliding window of length len(p), track character counts
need = Counter(p)
window = Counter(s[:len(p)])
result = []
if window == need:
result.append(0)
for i in range(len(p), len(s)):
window[s[i]] += 1
old = s[i - len(p)]
window[old] -= 1
if window[old] == 0:
del window[old]
if window == need:
result.append(i - len(p) + 1)
return result
# LeetCode 438 — O(n) with fixed-size window Counter comparison
def group_anagrams(words):
groups = defaultdict(list)
for word in words:
key = tuple(sorted(word)) # canonical form
groups[key].append(word)
return list(groups.values())
# LeetCode 49 — O(n * k log k) where k = avg word length
Pattern 4: KMP for Pattern Matching
Knuth-Morris-Pratt finds all occurrences of pattern P in text T in O(|T| + |P|) time, compared to O(|T| * |P|) for naive search.
def kmp_search(text, pattern):
# Build failure function (partial match table)
def build_lps(p):
lps = [0] * len(p)
length, i = 0, 1
while i < len(p):
if p[i] == p[length]:
length += 1
lps[i] = length
i += 1
elif length:
length = lps[length - 1]
else:
lps[i] = 0
i += 1
return lps
lps = build_lps(pattern)
matches = []
i = j = 0 # i = text index, j = pattern index
while i < len(text):
if text[i] == pattern[j]:
i += 1; j += 1
if j == len(pattern):
matches.append(i - j)
j = lps[j - 1]
elif i < len(text) and text[i] != pattern[j]:
j = lps[j - 1] if j else (i := i + 1) or 0
return matches
Pattern 5: Trie for Prefix Matching
class Trie:
def __init__(self):
self.children = {}
self.is_end = False
def insert(self, word):
node = self
for c in word:
node = node.children.setdefault(c, Trie())
node.is_end = True
def search(self, word):
node = self
for c in word:
if c not in node.children: return False
node = node.children[c]
return node.is_end
def starts_with(self, prefix):
node = self
for c in prefix:
if c not in node.children: return False
node = node.children[c]
return True
# Applications: autocomplete, spell check, word search II
Key Interview Tips
- Sliding window: two pointers moving in the same direction — right expands, left contracts
- When asked about substrings, think sliding window first; if that doesn’t work, think DP
- Anagram check: Counter(s) == Counter(t), O(n+m). Sorted string as hash key for grouping
- Palindrome: expand from center for longest palindrome; two-pointer from ends for validation
- Pattern matching in production: use built-in string methods (str.find(), re) — KMP is for interviews and understanding
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”When should I use a sliding window for string problems?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Use a sliding window when the problem asks for a contiguous substring satisfying some property — longest without repeating characters, minimum window containing all characters of a pattern, all anagrams of a pattern in a string. The template: expand the right pointer to include new characters; when the window violates the property, advance the left pointer to restore it. Time complexity is O(n) because each character enters and leaves the window at most once.”}},{“@type”:”Question”,”name”:”How do you check if two strings are anagrams in O(n)?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Use Counter (hash map of character frequencies): Counter(s) == Counter(t). This is O(n+m) time and O(k) space where k is the alphabet size. For fixed ASCII alphabets, use an array of 26 ints. For sliding-window anagram detection (find all anagrams of p in s): maintain a window of length len(p), increment the incoming character count and decrement the outgoing character count, compare window counter to target counter each step. Comparison of fixed-size counters is O(k), so total is O(n*k) ≈ O(n) for constant alphabet.”}},{“@type”:”Question”,”name”:”What is KMP and when do you need it?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Knuth-Morris-Pratt finds all occurrences of pattern P in text T in O(|T| + |P|) time, vs O(|T| * |P|) for naive search. The key insight: when a mismatch occurs at position j in the pattern, the failure function (LPS array) tells you the longest proper prefix of P[0..j] that is also a suffix — you can resume matching from there instead of starting over. In practice, use this for interviews and understanding; production code uses str.find(), Boyer-Moore in standard libraries, or regex engines.”}},{“@type”:”Question”,”name”:”How does a Trie differ from a hash map for string prefix lookups?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”A hash map gives O(k) lookup for exact matches (k = key length) but cannot answer prefix queries efficiently. A Trie gives O(k) lookup, O(k) prefix-existence check (starts_with), and O(k + results) for listing all words with a prefix — hash maps cannot do the last two without scanning all keys. Use a Trie for autocomplete (return all words with prefix), spell checking (find closest word), and word search in a grid. Hash maps are better for exact key-value lookup without prefix needs.”}},{“@type”:”Question”,”name”:”What is the expand-from-center approach for palindromes?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”For longest palindromic substring: instead of checking every O(n²) substring, observe that each palindrome has a center (single character for odd length, gap between two characters for even length). For each of the 2n-1 centers, expand outward as long as characters match. The longest expansion is the answer. Time: O(n²) but with small constant — practically fast. Manacher’s algorithm achieves O(n) by reusing previously computed expansion lengths, but the expand-from-center approach is what interviewers expect.”}}]}
Sliding window and string algorithm patterns are tested in Google coding interview questions.
String algorithms and pattern matching are covered in Meta coding interview preparation.
String manipulation and substring problems appear in Amazon coding interview guide.