String Manipulation Interview Patterns: Complete Guide (2025)
String problems are ubiquitous in coding interviews — from anagram detection to complex parsing. Mastering these patterns with Python’s rich string library will help you solve them efficiently. Tested at all major tech companies.
Pattern 1: Two Pointers on Strings
def is_palindrome(s: str) -> bool:
"""Valid palindrome considering only alphanumeric characters"""
left, right = 0, len(s) - 1
while left < right:
while left < right and not s[left].isalnum():
left += 1
while left str:
"""
LeetCode 5. Expand around center.
Time: O(n²), Space: O(1).
DP approach also O(n²) but O(n²) space.
Manacher's algorithm: O(n) but complex to implement.
"""
def expand(left: int, right: int) -> tuple[int, int]:
while left >= 0 and right end - start:
start, end = l, r
# Even-length palindromes (center between i and i+1)
l, r = expand(i, i + 1)
if r - l > end - start:
start, end = l, r
return s[start:end + 1]
def palindrome_partitioning_min_cuts(s: str) -> int:
"""
LeetCode 132. Min cuts to partition s into all palindromes.
DP: dp[i] = min cuts for s[0:i+1]
"""
n = len(s)
is_pal = [[False] * n for _ in range(n)]
# Pre-compute palindrome table
for end in range(n):
for start in range(end + 1):
if s[start] == s[end] and (end - start <= 2 or is_pal[start+1][end-1]):
is_pal[start][end] = True
dp = list(range(n)) # worst case: cut at every position
for end in range(1, n):
if is_pal[0][end]:
dp[end] = 0
continue
for start in range(1, end + 1):
if is_pal[start][end]:
dp[end] = min(dp[end], dp[start - 1] + 1)
return dp[n - 1]
Pattern 2: Sliding Window for Substrings
from collections import Counter
def minimum_window_substring(s: str, t: str) -> str:
"""
LeetCode 76. Minimum Window Substring containing all chars of t.
Classic sliding window with character frequency counting.
Time: O(|s| + |t|), Space: O(|s| + |t|)
"""
if not t or not s:
return ""
need = Counter(t) # chars we need and their counts
missing = len(t) # total characters still needed
best_left = 0
best_len = float('inf')
left = 0
for right, char in enumerate(s):
if need[char] > 0:
missing -= 1
need[char] -= 1
# Window contains all chars of t
if missing == 0:
# Shrink from left
while need[s[left]] < 0:
need[s[left]] += 1
left += 1
if right - left + 1 < best_len:
best_len = right - left + 1
best_left = left
# Move left one more to try smaller window
need[s[left]] += 1
missing += 1
left += 1
return s[best_left:best_left + best_len] if best_len int:
"""
LeetCode 340. Longest Substring with At Most K Distinct Characters.
"""
count = Counter()
left = 0
result = 0
for right in range(len(s)):
count[s[right]] += 1
while len(count) > k:
count[s[left]] -= 1
if count[s[left]] == 0:
del count[s[left]]
left += 1
result = max(result, right - left + 1)
return result
def longest_substring_no_repeat(s: str) -> int:
"""LeetCode 3. Longest Substring Without Repeating Characters."""
seen = {} # char -> last seen index
left = 0
result = 0
for right, char in enumerate(s):
if char in seen and seen[char] >= left:
left = seen[char] + 1 # jump left past previous occurrence
seen[char] = right
result = max(result, right - left + 1)
return result
Pattern 3: Anagram and Permutation
def is_anagram(s: str, t: str) -> bool:
"""Check if two strings are anagrams"""
return Counter(s) == Counter(t)
def find_all_anagrams(s: str, p: str) -> list[int]:
"""
LeetCode 438. Find all anagram starting positions of p in s.
Sliding window with character count comparison.
"""
if len(p) > len(s):
return []
p_count = Counter(p)
window = Counter(s[:len(p)])
result = []
if window == p_count:
result.append(0)
for i in range(len(p), len(s)):
# Add right char
window[s[i]] += 1
# Remove left char
left_char = s[i - len(p)]
window[left_char] -= 1
if window[left_char] == 0:
del window[left_char]
if window == p_count:
result.append(i - len(p) + 1)
return result
def group_anagrams(strs: list[str]) -> list[list[str]]:
"""
LeetCode 49. Group anagrams together.
Key: sorted string is the canonical anagram signature.
"""
groups = {}
for s in strs:
key = ''.join(sorted(s))
if key not in groups:
groups[key] = []
groups[key].append(s)
return list(groups.values())
Pattern 4: String Building and Parsing
def decode_string(s: str) -> str:
"""
LeetCode 394. Decode string like '3[a2[c]]' → 'accaccacc'.
Stack-based: track current string and repetition count.
"""
stack = []
current_str = ""
current_num = 0
for char in s:
if char.isdigit():
current_num = current_num * 10 + int(char)
elif char == '[':
stack.append((current_str, current_num))
current_str = ""
current_num = 0
elif char == ']':
prev_str, repeat = stack.pop()
current_str = prev_str + current_str * repeat
else:
current_str += char
return current_str
def simplify_path(path: str) -> str:
"""
LeetCode 71. Simplify Unix file path.
'/home/../usr//bin' → '/usr/bin'
"""
stack = []
for part in path.split('/'):
if part == '..':
if stack:
stack.pop()
elif part and part != '.':
stack.append(part)
return '/' + '/'.join(stack)
def integer_to_roman(num: int) -> str:
"""Convert integer to Roman numeral"""
val_sym = [
(1000, 'M'), (900, 'CM'), (500, 'D'), (400, 'CD'),
(100, 'C'), (90, 'XC'), (50, 'L'), (40, 'XL'),
(10, 'X'), (9, 'IX'), (5, 'V'), (4, 'IV'), (1, 'I')
]
result = []
for val, sym in val_sym:
while num >= val:
result.append(sym)
num -= val
return ''.join(result)
Pattern 5: String Matching (KMP Algorithm)
def kmp_search(text: str, pattern: str) -> list[int]:
"""
Knuth-Morris-Pratt string matching. O(n + m) time.
Returns all starting indices of pattern in text.
Key: build 'failure function' (partial match table) to avoid
redundant comparisons after a mismatch.
"""
if not pattern:
return list(range(len(text)))
# Build failure function (lps = longest proper prefix which is also suffix)
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
else:
if length != 0:
length = lps[length - 1] # Don't increment i
else:
lps[i] = 0
i += 1
# Search using LPS table
result = []
i = 0 # index in text
j = 0 # index in pattern
while i < len(text):
if text[i] == pattern[j]:
i += 1
j += 1
if j == m:
result.append(i - j) # Pattern found at index i-j
j = lps[j - 1] # Continue searching
elif i int:
"""
LeetCode 686. How many times to repeat a so b is a substring?
KMP to check if b is substring of a repeated enough times.
"""
# b can be a substring of a * ceil(len(b)/len(a)) or +1 repeats
times = (len(b) + len(a) - 1) // len(a) # ceil division
for t in [times, times + 1]:
if b in a * t:
return t
return -1
Common String Operations in Python
# Essential string methods for interviews
s = "Hello, World!"
# Case
s.lower(), s.upper(), s.title() # case conversion
s.isalnum(), s.isalpha(), s.isdigit() # character checks
# Search and split
s.find('World') # 7 (first index, -1 if not found)
s.count('l') # 3
s.split(', ') # ['Hello', 'World!']
s.split() # ['Hello,', 'World!'] (split on whitespace)
', '.join(['a', 'b', 'c']) # 'a, b, c'
# Strip
s.strip() # remove leading/trailing whitespace
s.lstrip('H') # 'ello, World!' (left strip chars)
s.replace('Hello', 'Hi') # 'Hi, World!'
# String as list of chars
chars = list(s)
chars.sort()
result = ''.join(chars) # sorted string
# Efficient string building (use join, not +=)
parts = []
for i in range(1000):
parts.append(str(i))
result = ''.join(parts) # O(n) vs += which is O(n²) for Python strings
# Character operations
ord('A') # 65 (ASCII value)
chr(65) # 'A'
ord(c) - ord('a') # 0-25 for lowercase letters
Interview Quick Reference
| Problem Type | Technique | Time |
|---|---|---|
| Palindrome check | Two pointers | O(n) |
| Longest palindromic substring | Expand around center | O(n²) |
| Min window substring | Sliding window + Counter | O(n) |
| Anagram detection | Counter comparison | O(n) |
| Group anagrams | Sorted string as key | O(nk log k) |
| Decode encoded string | Stack | O(n) |
| Pattern matching | KMP algorithm | O(n+m) |
| String building | List + join (not +=) | O(n) |
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”What are the most important string patterns for coding interviews?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Five core patterns: (1) Two pointers — palindrome checking, reversing words, valid palindrome with filtering. (2) Sliding window — minimum window substring, longest substring without repeating characters, find all anagrams. (3) Character frequency (Counter/HashMap) — anagram detection, group anagrams, character replacement. (4) Stack for parsing — decode string ‘3[a2[c]]’, simplify file paths, validate brackets. (5) String building — always use list + join instead of += for O(n) vs O(n²) complexity. These patterns cover 80% of LeetCode string problems.”}},{“@type”:”Question”,”name”:”How does the sliding window algorithm work for string problems?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Sliding window maintains a [left, right] window of characters and expands/contracts based on a condition. Pattern: expand right pointer to add characters, shrink left pointer when constraint is violated. For minimum window substring: right expands adding chars to window; when all target chars are covered, left shrinks to minimize window size, recording the minimum valid window found. Key implementation detail: use a Counter for character frequencies and a ‘missing’ count to avoid expensive Counter comparison on each step. Time: O(n) — each character is added and removed from window at most once.”}},{“@type”:”Question”,”name”:”What is the KMP algorithm and when should you use it in an interview?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Knuth-Morris-Pratt (KMP) is a linear-time O(n+m) string matching algorithm that avoids redundant comparisons after a mismatch. The key insight: build a ‘failure function’ (LPS array) for the pattern that tells you how far to jump back when a mismatch occurs. When to use in interview: if the interviewer explicitly asks about efficient string matching, or for problems like ‘find all occurrences of pattern in text’ where brute force O(n*m) is too slow. For most practical problems, Python’s in operator or str.find() uses optimized C implementations. Mentioning KMP shows depth; implementing it correctly under pressure is impressive but not always required.”}},{“@type”:”Question”,”name”:”How do you efficiently build strings in Python?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”String concatenation (s += char) creates a new string object each time: O(n²) total for n concatenations. Correct approach: collect parts in a list and join at the end. Example: result = []; for char in …: result.append(char); return ”.join(result) — O(n) total. ”.join() is also how you convert a list of chars back to string after sorting or filtering. Other efficient patterns: use list comprehension + join for filtering (”.join(c for c in s if c.isalnum())); use str.replace() for substitutions; use io.StringIO for complex string building in performance-critical code.”}},{“@type”:”Question”,”name”:”How do you reverse words in a string without extra space?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Three-step approach for reversing words in-place: (1) Reverse the entire string character by character, (2) Reverse each individual word, (3) Handle multiple spaces by collapsing them. In Python: ‘ ‘.join(reversed(s.split())) handles the common case in one line, splitting on whitespace automatically handles multiple spaces. For in-place (C/Java style): work with a char array — reverse the whole array, then reverse each word between spaces. This is a classic O(n) time, O(1) extra space solution. Python’s immutable strings mean you’d convert to a list first: chars = list(s); reverse(chars, 0, len(chars)-1); then reverse each word.”}}]}