String Algorithm Patterns in Interviews
String problems are ubiquitous in coding interviews. Most string challenges reduce to a small set of patterns: sliding window, two-pointer, hashing for equality checks, and recognizing palindrome/anagram structures. Mastering these patterns lets you solve novel problems by analogy.
Pattern 1: Sliding Window for Substrings
Use when: “find the shortest/longest substring satisfying a condition.” Maintain a window [left, right] and a frequency map of characters in the window.
Minimum Window Substring
Find the smallest substring of S containing all characters of T.
def min_window(s, t):
need = Counter(t)
window = defaultdict(int)
left = 0
formed = 0
required = len(need)
best = ""
for right, c in enumerate(s):
window[c] += 1
if c in need and window[c] == need[c]:
formed += 1
while formed == required:
if not best or right - left + 1 < len(best):
best = s[left:right+1]
window[s[left]] -= 1
if s[left] in need and window[s[left]] < need[s[left]]:
formed -= 1
left += 1
return best
Time: O(|S| + |T|). The key: track how many characters are “satisfied” (window count >= need count) with the formed variable. Shrink from left when all characters are satisfied to find the minimum window.
Longest Substring Without Repeating Characters
Move right pointer, add to window. If character already in window: advance left pointer until duplicate is removed. Track max window size.
Permutation in String / Find All Anagrams
Fixed-size sliding window of length len(p). Check if window’s character counts match p’s counts. Use a difference counter: count of characters where window differs from target. When difference count = 0, window is an anagram.
Pattern 2: Two-Pointer for Palindromes
Longest Palindromic Substring
Expand from center: for each position i, try expanding a palindrome around center i (odd length) and between i and i+1 (even length). O(N²) time, O(1) space. Manacher’s algorithm solves this in O(N) but is complex — O(N²) is acceptable in interviews.
Valid Palindrome II (One Deletion Allowed)
Two pointers from both ends. When characters mismatch, try skipping left pointer OR right pointer — if either resulting substring is a palindrome, return True. Helper function is_palindrome(s, l, r) checks the range.
Pattern 3: Hashing for String Matching
Rabin-Karp Rolling Hash
Compute hash of pattern. Slide a window of pattern length across text, updating the hash in O(1) by subtracting the contribution of the character leaving the window and adding the character entering. Compare hashes; only do expensive string comparison on hash match.
def rabin_karp(text, pattern):
BASE, MOD = 31, 10**9 + 7
n, m = len(text), len(pattern)
if m > n: return []
power = pow(BASE, m-1, MOD)
p_hash = t_hash = 0
for i in range(m):
p_hash = (p_hash * BASE + ord(pattern[i])) % MOD
t_hash = (t_hash * BASE + ord(text[i])) % MOD
results = []
for i in range(n - m + 1):
if t_hash == p_hash and text[i:i+m] == pattern:
results.append(i)
if i + m < n:
t_hash = (t_hash - ord(text[i]) * power) % MOD
t_hash = (t_hash * BASE + ord(text[i+m])) % MOD
return results
Pattern 4: Trie for Multi-Pattern Matching
When searching for multiple patterns simultaneously, a Trie is more efficient than running Rabin-Karp for each pattern separately. Insert all patterns into a Trie; traverse text through the Trie. Used for word search in grids (Word Search II), autocomplete, and IP routing.
Pattern 5: Encode and Decode Strings
Interview favorite: encode a list of strings into a single string, then decode back. Naive approach (join with delimiter) fails if strings contain the delimiter. Robust solution: length-prefix encoding.
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
Pattern 6: Z-Algorithm for Pattern Search
Z[i] = length of the longest substring starting at i that is also a prefix of the string. Build Z array in O(N). For pattern search: concatenate pattern + “$” + text, compute Z array. Position i where Z[i] == len(pattern) is a match location. Simpler than KMP to implement in interviews.
Common String Interview Problems by Pattern
- Sliding window: Minimum Window Substring, Longest Substring Without Repeating Characters, Fruit Into Baskets
- Palindrome two-pointer: Longest Palindromic Substring, Valid Palindrome, Palindrome Partitioning
- Anagram/frequency: Group Anagrams, Find All Anagrams, Valid Anagram
- Hashing/rolling hash: Repeated DNA Sequences, Longest Duplicate Substring
- String DP: Edit Distance, Longest Common Subsequence, Word Break, Regular Expression Matching
Interview Tips
- For any “substring” problem, start by asking: fixed or variable window size? This determines your approach.
- Anagram detection: sort both strings O(N log N) or use Counter comparison O(N). For sliding window anagram: track a “matches” count to avoid recomputing equality O(N) at each step.
- Distinguish character set: lowercase English only (26 chars, can use array), Unicode (use hash map).
- Rolling hash is the key idea behind Rabin-Karp — make sure you handle the modular arithmetic carefully (add MOD before taking % to avoid negative values).
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “How do you solve Minimum Window Substring and what is the key insight?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Minimum Window Substring: find the shortest substring of S that contains all characters of T. The key insight: use a sliding window with a "formed" counter that tracks how many distinct characters currently satisfy their required count. Expand right pointer to include characters; when all characters are satisfied (formed == len(need)), shrink from left pointer to minimize the window while staying valid. The trick: only increment "formed" when a character's count in the window exactly reaches its required count (not for every increment). This avoids recounting all characters at each step, keeping the algorithm O(|S| + |T|) instead of O(|S| * |T|).” }
},
{
“@type”: “Question”,
“name”: “What is the rolling hash technique and when should you use it?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Rolling hash (Rabin-Karp): computes a hash for a window of characters in O(1) by subtracting the outgoing character's contribution and adding the incoming character's contribution. Hash = sum(char[i] * BASE^(m-1-i)) mod MOD for a window of size m. When the window slides: new_hash = (old_hash – char[left] * BASE^(m-1)) * BASE + char[right+1]. Use rolling hash when: (1) searching for a fixed-length pattern in text — O(N) average vs O(N*M) naive, (2) finding duplicate substrings of length k — hash all k-length windows, look for hash collisions, (3) Longest Duplicate Substring — binary search on length + rolling hash for O(N log N) solution. Always verify hash matches with actual string comparison (hash collisions are rare but possible with a single hash; use double hashing to reduce collision probability).” }
},
{
“@type”: “Question”,
“name”: “How do you group anagrams efficiently?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Group anagrams: given a list of strings, group strings that are anagrams of each other. Two approaches: (1) Sort each string and use it as a key: "eat" → "aet", "tea" → "aet" — same key means same anagram group. O(N * K log K) where K is max string length. (2) Count character frequencies and use the count tuple as a key: Counter("eat") == Counter("tea") — compare as a tuple of 26 counts. O(N * K). Both are correct and commonly seen in interviews. For approach 2, use a tuple (count['a'], count['b'], …, count['z']) as the dict key. The sorted-key approach is more readable; the count-tuple approach is faster for longer strings.” }
}
]
}