String Interview Patterns: Anagram, Palindrome, KMP & More
String problems are among the most common in coding interviews. Beyond brute-force O(n²) approaches, several patterns cut complexity to O(n) or O(n log n).
Pattern 1: Anagram and Character Frequency
from collections import Counter
# Check if two strings are anagrams
def is_anagram(s, t):
return Counter(s) == Counter(t)
# or: sorted(s) == sorted(t) — O(n log n)
# Group anagrams together
def group_anagrams(strs):
groups = {}
for s in strs:
key = tuple(sorted(s)) # canonical form
groups.setdefault(key, []).append(s)
return list(groups.values())
# Find all anagrams of p in s
def find_anagrams(s, p):
need = Counter(p)
window = Counter()
result = []
k = len(p)
for i, ch in enumerate(s):
window[ch] += 1
if i >= k:
old = s[i - k]
window[old] -= 1
if window[old] == 0:
del window[old]
if window == need:
result.append(i - k + 1)
return result
Pattern 2: Palindrome Checks
# Valid palindrome (ignore non-alphanumeric)
def is_palindrome(s):
lo, hi = 0, len(s) - 1
while lo < hi:
while lo < hi and not s[lo].isalnum(): lo += 1
while lo = 0 and r len(result): result = odd
if len(even) > len(result): result = even
return result
# Count palindromic substrings
def count_substrings(s):
count = 0
for i in range(len(s)):
for l, r in [(i, i), (i, i+1)]: # odd and even centers
while l >= 0 and r < len(s) and s[l] == s[r]:
count += 1; l -= 1; r += 1
return count
Pattern 3: KMP — Pattern Matching in O(n)
KMP avoids re-comparing matched characters. The failure function (lps array) pre-computes the longest proper prefix that is also a suffix for each prefix of the pattern.
def kmp_search(text, pattern):
# Build failure function
m = len(pattern)
lps = [0] * m
length = 0
i = 1
while i < m:
if pattern[i] == pattern[length]:
length += 1
lps[i] = length
i += 1
elif length:
length = lps[length - 1]
else:
lps[i] = 0
i += 1
# Search
matches = []
i = j = 0
while i < len(text):
if text[i] == pattern[j]:
i += 1; j += 1
if j == m:
matches.append(i - j)
j = lps[j - 1]
elif i < len(text) and text[i] != pattern[j]:
if j: j = lps[j - 1]
else: i += 1
return matches
Pattern 4: Roman Numerals and String Conversion
def int_to_roman(num):
vals = [1000,900,500,400,100,90,50,40,10,9,5,4,1]
syms = ["M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"]
result = ""
for v, s in zip(vals, syms):
while num >= v:
result += s; num -= v
return result
def roman_to_int(s):
val = {'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
result = 0
for i in range(len(s)):
if i < len(s)-1 and val[s[i]] < val[s[i+1]]:
result -= val[s[i]]
else:
result += val[s[i]]
return result
Pattern 5: Encode and Decode Strings
# Length-prefix encoding (handles any characters including delimiters)
def encode(strs):
return "".join(f"{len(s)}#{s}" for s in strs)
def decode(s):
result = []
i = 0
while i < len(s):
j = s.index('#', i)
length = int(s[i:j])
result.append(s[j+1:j+1+length])
i = j + 1 + length
return result
Classic String Interview Problems
| Problem | Pattern | Complexity |
|---|---|---|
| Valid Anagram | Counter comparison | O(n) |
| Group Anagrams | Sorted key / char count key | O(n·k log k) |
| Longest Palindromic Substring | Expand around center | O(n²) |
| Valid Parentheses | Stack | O(n) |
| Implement strStr() / KMP | KMP failure function | O(n+m) |
| Longest Common Prefix | Vertical scan or sort | O(n·m) |
| String to Integer (atoi) | State machine | O(n) |
| Zigzag Conversion | Row cycling | O(n) |