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
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.