# String Algorithm Patterns for Coding Interviews

Source: https://www.techinterview.org/post/3233467640/string-algorithm-patterns/
Updated: 2026-04-17 · techinterview.org

## Why String Algorithms Matter in Interviews

String problems are ubiquitous in technical interviews at Google, Meta, Amazon, and Microsoft. Key patterns: sliding window for substring problems, two pointers for palindrome and reversal, hashing for anagram detection, and KMP/Rabin-Karp for pattern matching. Recognizing the right pattern for a string problem is the skill that distinguishes candidates who struggle with O(n²) solutions from those who solve in O(n).

## Pattern 1: Sliding Window for Substrings

Use a sliding window when the problem asks for "the longest/shortest substring with property X." Expand right, contract left when the property is violated.


```
def longest_substring_without_repeat(s):
    char_index = {}
    left = max_len = 0
    for right, c in enumerate(s):
        if c in char_index and char_index[c] >= left:
            left = char_index[c] + 1  # shrink window
        char_index[c] = right
        max_len = max(max_len, right - left + 1)
    return max_len
# LeetCode 3 — O(n) time, O(k) space where k = charset size

def min_window_substring(s, t):
    need = Counter(t)
    have, total = 0, len(need)
    window = {}
    left = best = best_l = 0
    best_r = float('inf')
    for right, c in enumerate(s):
        window[c] = window.get(c, 0) + 1
        if c in need and window[c] == need[c]:
            have += 1
        while have == total:
            if right - left < best_r - best_l:
                best_l, best_r = left, right
            window[s[left]] -= 1
            if s[left] in need and window[s[left]] < need[s[left]]:
                have -= 1
            left += 1
    return s[best_l:best_r+1] if best_r != float('inf') else ''
# LeetCode 76 — O(|s| + |t|)
```


## Pattern 2: Two Pointers for Palindromes


```
def longest_palindrome(s):
    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]

    result = ''
    for i in range(len(s)):
        odd  = expand(i, i)      # odd-length palindrome
        even = expand(i, i+1)    # even-length palindrome
        result = max(result, odd, even, key=len)
    return result
# LeetCode 5 — O(n²) but optimal for this problem formulation

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1; right -= 1
    return True
```


## Pattern 3: Hashing for Anagrams


```
from collections import Counter

def find_all_anagrams(s, p):
    # Sliding window of length len(p), track character counts
    need = Counter(p)
    window = Counter(s[:len(p)])
    result = []
    if window == need:
        result.append(0)

    for i in range(len(p), len(s)):
        window[s[i]] += 1
        old = s[i - len(p)]
        window[old] -= 1
        if window[old] == 0:
            del window[old]
        if window == need:
            result.append(i - len(p) + 1)
    return result
# LeetCode 438 — O(n) with fixed-size window Counter comparison

def group_anagrams(words):
    groups = defaultdict(list)
    for word in words:
        key = tuple(sorted(word))  # canonical form
        groups[key].append(word)
    return list(groups.values())
# LeetCode 49 — O(n * k log k) where k = avg word length
```


## Pattern 4: KMP for Pattern Matching

Knuth-Morris-Pratt finds all occurrences of pattern P in text T in O(|T| + |P|) time, compared to O(|T| * |P|) for naive search.


```
def kmp_search(text, pattern):
    # Build failure function (partial match table)
    def build_lps(p):
        lps = [0] * len(p)
        length, i = 0, 1
        while i < len(p):
            if p[i] == p[length]:
                length += 1
                lps[i] = length
                i += 1
            elif length:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
        return lps

    lps = build_lps(pattern)
    matches = []
    i = j = 0  # i = text index, j = pattern index
    while i < len(text):
        if text[i] == pattern[j]:
            i += 1; j += 1
        if j == len(pattern):
            matches.append(i - j)
            j = lps[j - 1]
        elif i < len(text) and text[i] != pattern[j]:
            j = lps[j - 1] if j else (i := i + 1) or 0
    return matches
```


## Pattern 5: Trie for Prefix Matching


```
class Trie:
    def __init__(self):
        self.children = {}
        self.is_end = False

    def insert(self, word):
        node = self
        for c in word:
            node = node.children.setdefault(c, Trie())
        node.is_end = True

    def search(self, word):
        node = self
        for c in word:
            if c not in node.children: return False
            node = node.children[c]
        return node.is_end

    def starts_with(self, prefix):
        node = self
        for c in prefix:
            if c not in node.children: return False
            node = node.children[c]
        return True

# Applications: autocomplete, spell check, word search II
```


## Key Interview Tips

  - Sliding window: two pointers moving in the same direction — right expands, left contracts

  - When asked about substrings, think sliding window first; if that doesn't work, think DP

  - Anagram check: Counter(s) == Counter(t), O(n+m). Sorted string as hash key for grouping

  - Palindrome: expand from center for longest palindrome; two-pointer from ends for validation

  - Pattern matching in production: use built-in string methods (str.find(), re) — KMP is for interviews and understanding

Sliding window and string algorithm patterns are tested in [Google coding interview questions](https://www.techinterview.org/post/3233460274/netflix-interview-guide-2026-streaming-architecture-recommendation-systems-and-engineering-excellence/).

String algorithms and pattern matching are covered in [Meta coding interview preparation](https://www.techinterview.org/post/3233460272/meta-interview-guide-2026-facebook-instagram-whatsapp-engineering/).

String manipulation and substring problems appear in [Amazon coding interview guide](https://www.techinterview.org/post/3233460275/scale-ai-interview-guide-2026-data-infrastructure-rlhf-pipelines-and-ml-engineering/).