String and Array Patterns Overview
String and array manipulation problems are a staple of coding interviews at every level. The patterns repeat across dozens of problems — recognizing the underlying structure is more valuable than memorizing individual solutions. This guide covers the most frequently tested patterns with the canonical implementation for each.
Pattern 1: Character Frequency Map (Anagrams)
Problems: valid anagram, group anagrams, find all anagrams in a string, first unique character. The core operation: count character frequencies and compare.
from collections import Counter
def is_anagram(s: str, t: str) -> bool:
return Counter(s) == Counter(t) # O(N), O(1) space (26 lowercase letters)
def group_anagrams(strs):
groups = {}
for s in strs:
key = tuple(sorted(s)) # canonical form: sorted chars
groups.setdefault(key, []).append(s)
return list(groups.values())
# Sliding window anagram (LeetCode 438):
def find_anagrams(s: str, p: str):
result = []
need = Counter(p)
window = Counter(s[:len(p)])
if window == need:
result.append(0)
for i in range(len(p), len(s)):
window[s[i]] += 1
left = s[i - len(p)]
window[left] -= 1
if window[left] == 0:
del window[left]
if window == need:
result.append(i - len(p) + 1)
return result
Pattern 2: Palindrome Checking and Expansion
A palindrome reads the same forwards and backwards. Two techniques: (1) two-pointer from both ends, (2) expand-around-center for substrings.
def is_palindrome(s: str) -> bool:
# Clean version: alphanumeric only, case-insensitive
filtered = [c.lower() for c in s if c.isalnum()]
return filtered == filtered[::-1]
def longest_palindromic_substring(s: str) -> str:
# Expand around center: O(N^2) time, O(1) space
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] # last valid bounds
result = ""
for i in range(len(s)):
# Odd-length palindromes (center at i)
odd = expand(i, i)
# Even-length palindromes (center between i and i+1)
even = expand(i, i+1)
result = max(result, odd, even, key=len)
return result
# LeetCode 5: Longest Palindromic Substring
# LeetCode 647: Count palindromic substrings (count instead of track longest)
# Manacher's algorithm: O(N) — useful to know exists
Pattern 3: Subarray Sum (Prefix Sum)
For subarray sum queries, prefix sums enable O(1) range queries after O(N) preprocessing. For “subarray sum equals k” use a hashmap of prefix sums.
def subarray_sum_equals_k(nums, k) -> int:
count = 0
prefix = 0
freq = {0: 1} # prefix 0 exists once (empty prefix)
for n in nums:
prefix += n
# If prefix - k was seen, there is a subarray summing to k
count += freq.get(prefix - k, 0)
freq[prefix] = freq.get(prefix, 0) + 1
return count
# LeetCode 560: Subarray Sum Equals K
# LeetCode 974: Subarray Sums Divisible by K (use prefix % k as key)
# LeetCode 523: Continuous Subarray Sum (prefix mod k, check gap >= 2)
def max_subarray(nums) -> int:
# Kadane's algorithm: O(N)
max_sum = curr = nums[0]
for n in nums[1:]:
curr = max(n, curr + n)
max_sum = max(max_sum, curr)
return max_sum
Pattern 4: Next Permutation
Find the lexicographically next greater permutation of a number sequence. Three steps: (1) find the rightmost element smaller than its right neighbor (pivot), (2) find the smallest element to the right of pivot that is larger than pivot, (3) swap them, reverse the suffix.
def next_permutation(nums) -> None:
n = len(nums)
# Step 1: find pivot (rightmost i where nums[i] = 0 and nums[i] >= nums[i+1]:
i -= 1
if i >= 0:
# Step 2: find rightmost element > nums[i]
j = n - 1
while nums[j] <= nums[i]:
j -= 1
nums[i], nums[j] = nums[j], nums[i]
# Step 3: reverse the suffix after i
nums[i+1:] = nums[i+1:][::-1]
# LeetCode 31: Next Permutation
# LeetCode 60: Permutation Sequence (use factorial number system)
Pattern 5: Matrix Rotation and Spiral Traversal
def rotate_90_clockwise(matrix) -> None:
# In-place: transpose then reverse each row
n = len(matrix)
# Transpose (reflect across main diagonal)
for i in range(n):
for j in range(i+1, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# Reverse each row
for row in matrix:
row.reverse()
# Rotate counter-clockwise: reverse each row first, then transpose
def spiral_order(matrix):
result = []
top, bottom = 0, len(matrix) - 1
left, right = 0, len(matrix[0]) - 1
while top <= bottom and left <= right:
for c in range(left, right+1): result.append(matrix[top][c])
top += 1
for r in range(top, bottom+1): result.append(matrix[r][right])
right -= 1
if top <= bottom:
for c in range(right, left-1, -1): result.append(matrix[bottom][c])
bottom -= 1
if left <= right:
for r in range(bottom, top-1, -1): result.append(matrix[r][left])
left += 1
return result
# LeetCode 48: Rotate Image
# LeetCode 54/59: Spiral Matrix I and II
Pattern 6: String Compression and Encoding
def compress(chars) -> int:
# In-place run-length encoding (LeetCode 443)
write = 0
i = 0
while i < len(chars):
c = chars[i]
count = 0
while i 1:
for digit in str(count):
chars[write] = digit
write += 1
return write
def decode_string(s: str) -> str:
# LeetCode 394: "3[a2[c]]" -> "accaccacc"
stack = []
curr = ""
k = 0
for c in s:
if c.isdigit():
k = k * 10 + int(c)
elif c == "[":
stack.append((curr, k))
curr, k = "", 0
elif c == "]":
prev, rep = stack.pop()
curr = prev + curr * rep
else:
curr += c
return curr
Key Pattern Recognition Guide
- Character counts / anagrams: Counter or 26-element array
- Longest palindrome substring: expand-around-center, O(N²)
- “Find subarray summing to k”: prefix sum + hashmap, O(N)
- Maximum subarray sum: Kadane’s algorithm, O(N)
- Next permutation: find pivot, swap, reverse suffix
- Matrix rotation 90°: transpose + reverse rows (in-place, O(1) extra space)
- Spiral traversal: four pointers (top, bottom, left, right), shrink inward