# String Interview Patterns

Source: https://www.techinterview.org/post/3233466852/string-patterns/
Updated: 2026-07-05 · techinterview.org

Strings appear in roughly 25-30% of coding interviews. Unlike arrays or trees, string problems have a concentrated set of patterns - master these and most string problems become recognizable variants.

## Sliding Window for Substring Problems

The sliding window pattern solves most "find a substring satisfying condition X" problems in O(n).


```
from collections import defaultdict

def min_window_substring(s: str, t: str) -> str:
    """LC 76 - Minimum Window Substring"""
    need = defaultdict(int)
    for c in t:
        need[c] += 1

    have, required = 0, len(need)
    window = defaultdict(int)
    left = 0
    result = ""
    min_len = float('inf')

    for right, c in enumerate(s):
        window[c] += 1
        if c in need and window[c] == need[c]:
            have += 1

        while have == required:
            # Update result
            if right - left + 1 < min_len:
                min_len = right - left + 1
                result = s[left:right+1]
            # Shrink window
            left_c = s[left]
            window[left_c] -= 1
            if left_c in need and window[left_c] < need[left_c]:
                have -= 1
            left += 1

    return result


def longest_substring_without_repeat(s: str) -> int:
    """LC 3 - Longest Substring Without Repeating Characters"""
    seen = {}
    left = 0
    best = 0
    for right, c in enumerate(s):
        if c in seen and seen[c] >= left:
            left = seen[c] + 1
        seen[c] = right
        best = max(best, right - left + 1)
    return best


def find_anagrams(s: str, p: str) -> list:
    """LC 438 - Find All Anagrams in a String"""
    if len(p) > len(s):
        return []

    p_count = [0] * 26
    w_count = [0] * 26
    for c in p:
        p_count[ord(c) - ord('a')] += 1

    result = []
    for i, c in enumerate(s):
        w_count[ord(c) - ord('a')] += 1
        if i >= len(p):
            out = s[i - len(p)]
            w_count[ord(out) - ord('a')] -= 1
        if w_count == p_count:
            result.append(i - len(p) + 1)
    return result
```


**Template recognition:** If the problem asks for a substring (contiguous) satisfying some count/frequency constraint, reach for sliding window first.

## KMP (Knuth-Morris-Pratt) Pattern Matching

Brute-force string search is O(n*m). KMP achieves O(n+m) by precomputing a failure function that tells us how much to advance the pattern pointer on mismatch.


```
def build_failure_function(pattern: str) -> list:
    """
    failure[i] = length of longest proper prefix of pattern[0..i]
    that is also a suffix.
    """
    m = len(pattern)
    failure = [0] * m
    j = 0  # length of previous longest prefix-suffix

    for i in range(1, m):
        while j > 0 and pattern[i] != pattern[j]:
            j = failure[j - 1]  # fall back
        if pattern[i] == pattern[j]:
            j += 1
        failure[i] = j

    return failure


def kmp_search(text: str, pattern: str) -> list:
    """Returns all start indices where pattern occurs in text."""
    if not pattern:
        return list(range(len(text) + 1))

    failure = build_failure_function(pattern)
    matches = []
    j = 0  # number of chars matched in pattern

    for i, c in enumerate(text):
        while j > 0 and c != pattern[j]:
            j = failure[j - 1]
        if c == pattern[j]:
            j += 1
        if j == len(pattern):
            matches.append(i - j + 1)
            j = failure[j - 1]

    return matches


# Example
print(kmp_search("ababcababcabc", "ababc"))  # [0, 5, 7]
```


**When KMP matters in interviews:** Most interviewers accept Python's `str.find()` or `in` operator. Knowing KMP signals depth. Bring it up proactively: "I'd use KMP here for O(n+m) - want me to implement the failure function?"

## Rabin-Karp Rolling Hash

Rolling hash enables O(1) hash recomputation as you slide a window, making O(n) substring search possible.


```
def rabin_karp(text: str, pattern: str) -> list:
    """Find all occurrences of pattern in text using rolling hash."""
    n, m = len(text), len(pattern)
    if m > n:
        return []

    BASE = 31
    MOD = 10**9 + 7
    matches = []

    def char_val(c):
        return ord(c) - ord('a') + 1

    # Precompute BASE^m mod MOD
    base_m = pow(BASE, m, MOD)

    # Initial hash for pattern and first window
    p_hash = 0
    t_hash = 0
    for i in range(m):
        p_hash = (p_hash * BASE + char_val(pattern[i])) % MOD
        t_hash = (t_hash * BASE + char_val(text[i])) % MOD

    for i in range(n - m + 1):
        if t_hash == p_hash:
            # Verify to handle hash collisions
            if text[i:i+m] == pattern:
                matches.append(i)
        if i < n - m:
            # Roll the hash: remove leading char, add next char
            t_hash = (t_hash * BASE - char_val(text[i]) * base_m + char_val(text[i + m])) % MOD

    return matches


# Example
print(rabin_karp("abcabcabc", "abc"))  # [0, 3, 6]


def longest_dup_substring(s: str) -> str:
    """LC 1044 - binary search on length + Rabin-Karp"""
    def has_duplicate(length: int) -> str:
        BASE, MOD = 31, 10**9 + 7
        base_l = pow(BASE, length, MOD)
        h = 0
        for c in s[:length]:
            h = (h * BASE + ord(c)) % MOD
        seen = {h: [0]}
        for i in range(1, len(s) - length + 1):
            h = (h * BASE - ord(s[i-1]) * base_l + ord(s[i+length-1])) % MOD
            for start in seen.get(h, []):
                if s[start:start+length] == s[i:i+length]:
                    return s[i:i+length]
            seen.setdefault(h, []).append(i)
        return ""

    lo, hi, result = 1, len(s) - 1, ""
    while lo <= hi:
        mid = (lo + hi) // 2
        found = has_duplicate(mid)
        if found:
            result = found
            lo = mid + 1
        else:
            hi = mid - 1
    return result
```


## Anagram and Character Frequency Patterns


```
from collections import Counter

def group_anagrams(strs: list) -> list:
    """LC 49 - Group Anagrams"""
    groups = defaultdict(list)
    for s in strs:
        key = tuple(sorted(s))  # or Counter(s) as frozenset
        groups[key].append(s)
    return list(groups.values())


def is_anagram(s: str, t: str) -> bool:
    """LC 242 - Valid Anagram - O(n) with Counter"""
    return Counter(s) == Counter(t)


def find_anagrams_freq(s: str, p: str) -> list:
    """LC 438 using Counter diff - cleaner but slightly slower"""
    result = []
    p_count = Counter(p)
    w_count = Counter(s[:len(p)])
    if w_count == p_count:
        result.append(0)

    for i in range(len(p), len(s)):
        # Add new character
        w_count[s[i]] += 1
        # Remove old character
        old = s[i - len(p)]
        w_count[old] -= 1
        if w_count[old] == 0:
            del w_count[old]
        if w_count == p_count:
            result.append(i - len(p) + 1)

    return result
```


**Interview tip:** Counter comparison is O(k) where k = unique characters. For fixed alphabets (26 letters) this is O(1) effectively. Mention this.

## Palindrome Patterns


```
def longest_palindrome_expand(s: str) -> str:
    """LC 5 - expand around center, O(n^2) time O(1) space"""
    def expand(left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left + 1:right]

    if not s:
        return ""
    longest = ""
    for i in range(len(s)):
        # Odd length palindrome, single center
        odd = expand(i, i)
        if len(odd) > len(longest):
            longest = odd
        # Even length palindrome, double center
        even = expand(i, i + 1)
        if len(even) > len(longest):
            longest = even
    return longest


def count_palindromic_substrings(s: str) -> int:
    """LC 647 - count all palindromic substrings"""
    count = 0
    for i in range(len(s)):
        for left, right in [(i, i), (i, i+1)]:
            while left >= 0 and right < len(s) and s[left] == s[right]:
                count += 1
                left -= 1
                right += 1
    return count
```


**Manacher's algorithm** solves LC 5 in O(n) time by reusing previously computed palindrome lengths. The key insight: if we are inside a larger palindrome, the mirror position gives us a lower bound on the current position's palindrome length. In practice, expand-around-center O(n^2) is accepted in most interviews - bring up Manacher's as an optimization if asked.

## String Encoding and Decoding


```
def encode(strs: list) -> str:
    """LC 271 - encode list of strings for transmission"""
    # Format: length#string for each entry
    # "4#lint6#coding4#is3#fun" -> ["lint","coding","is","fun"]
    return ''.join(f"{len(s)}#{s}" for s in strs)

def decode(s: str) -> list:
    result = []
    i = 0
    while i < len(s):
        j = i
        while s[j] != '#':
            j += 1
        length = int(s[i:j])
        j += 1
        result.append(s[j:j + length])
        i = j + length
    return result


def run_length_encode(s: str) -> str:
    """Classic RLE: 'aaabbc' -> '3a2b1c'"""
    if not s:
        return ""
    result = []
    count = 1
    for i in range(1, len(s)):
        if s[i] == s[i-1]:
            count += 1
        else:
            result.append(f"{count}{s[i-1]}")
            count = 1
    result.append(f"{count}{s[-1]}")
    return ''.join(result)
```


## Two-Pointer on Strings


```
def reverse_vowels(s: str) -> str:
    """LC 345"""
    vowels = set('aeiouAEIOU')
    chars = list(s)
    left, right = 0, len(chars) - 1
    while left < right:
        while left < right and chars[left] not in vowels:
            left += 1
        while left < right and chars[right] not in vowels:
            right -= 1
        chars[left], chars[right] = chars[right], chars[left]
        left += 1
        right -= 1
    return ''.join(chars)


def reverse_words(s: str) -> str:
    """LC 151 - Reverse Words in a String"""
    return ' '.join(s.split()[::-1])


def is_palindrome(s: str) -> bool:
    """LC 125 - Valid Palindrome (alphanumeric only)"""
    cleaned = [c.lower() for c in s if c.isalnum()]
    return cleaned == cleaned[::-1]
    # Two-pointer version for O(1) space:
    # left, right = 0, len(s)-1
    # while left < right:
    #     while left<right and not s[left].isalnum(): left+=1
    #     while left<right and not s[right].isalnum(): right-=1
    #     if s[left].lower() != s[right].lower(): return False
    #     left+=1; right-=1
    # return True
```


## Pattern Recognition Table

| Problem Type | Technique | Key Examples |
| --- | --- | --- |
| Find substring with constraint | Sliding window | LC 3, 76, 438 |
| Find pattern in text (one-off) | str.find() or KMP | LC 28 |
| Find repeated/duplicate substrings | Rabin-Karp + binary search | LC 1044, 718 |
| Are two strings anagrams | Counter / frequency array | LC 49, 242, 438 |
| Find longest palindromic substring | Expand around center | LC 5, 647 |
| Serialize/deserialize strings | Length-prefix encoding | LC 271 |
| In-place string reversal | Two pointers | LC 125, 151, 345 |
| Edit distance / alignment | DP (2D table) | LC 72, 1143 |
| Multiple pattern search | Aho-Corasick (rare in interviews) | LC 212 (use Trie instead) |

**Interview approach:** State the pattern aloud before coding. "This looks like a sliding window with frequency tracking - similar to minimum window substring." This signals pattern recognition and gives the interviewer confidence before you write a single line of code.

Meta coding interviews heavily test string patterns. See common questions for [Meta interview: string and substring problems](https://www.techinterview.org/post/3233460272/meta-interview-guide-2026-facebook-instagram-whatsapp-engineering/).

Apple coding rounds test string algorithms including KMP and sliding window. See patterns for [Apple interview: string manipulation and matching](https://www.techinterview.org/post/3233460277/apple-interview-guide-2026-ios-systems-hardware-software-integration-and-icloud-architecture/).

Atlassian coding rounds include string manipulation and pattern matching. See patterns for [Atlassian interview: string and text processing problems](https://www.techinterview.org/post/3233459919/atlassian-interview/).