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) |
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “What is the most efficient algorithm for pattern matching in a string?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “The KMP (Knuth-Morris-Pratt) algorithm finds all occurrences of a pattern in a text in O(n + m) time, where n is text length and m is pattern length. It pre-computes a "failure function" (LPS array) that records the longest proper prefix of the pattern that is also a suffix. This allows skipping ahead in the text when a mismatch occurs, avoiding redundant comparisons. Python's built-in str.find() also uses an optimized algorithm, but knowing KMP demonstrates understanding of the underlying approach.” }
},
{
“@type”: “Question”,
“name”: “How do you find all anagram substrings of a pattern in a text?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Use a sliding window of size len(p) with character frequency counters. Initialize the window with the first len(p) characters. Slide right: add the new character and remove the leftmost. If the window's frequency counter matches the pattern's counter, you found an anagram. Time O(n), space O(1) since there are only 26 possible characters. Use Python Counter for readability or an array of 26 counts for performance.” }
},
{
“@type”: “Question”,
“name”: “What is the expand-around-center approach for finding palindromes?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “For each character (and gap between characters), expand outward as long as characters match. This handles both odd-length (centered at character) and even-length (centered at gap) palindromes. For the longest palindromic substring: try both odd and even centers at each position, keep track of the longest found. Time O(n²), space O(1). The O(n) Manacher's algorithm uses a similar idea but leverages previously computed palindromes to avoid redundant work.” }
}
]
}