String Interview Patterns: Complete Guide

Intermediate 22 min read

What you'll learn

✓The top 20 string patterns that cover 90% of interview problems
✓Two-pointer technique applied to string problems
✓Frequency map technique for anagrams and permutations
✓Sliding window template for substring problems
✓When to use Trie vs HashMap vs sorting
✓Common mistakes that cost offers
✓Complexity cheatsheet for quick reference

Prerequisites

•Python string basics — see Strings Intro
•Sliding window — see Sliding Window on Strings
•Trie basics — see Trie Applications
•Big O notation — see Big-O Explained

String interview patterns

String problems show up in every coding interview round. They range from trivial (reverse a string) to brutal (minimum window substring, word break II). The difference between candidates who ace them and those who struggle is not intelligence — it is pattern recognition. This guide maps out the 20 patterns that cover the vast majority of string interview questions, with templates you can apply immediately.

The 20 string patterns

Here is the complete map. Each pattern links to the technique, typical problems, and the complexity you should target.

Pattern 1: Two pointers from both ends

Move left and right pointers toward each other. Used for palindromes, reversals, and partitioning.

def is_palindrome(s: str) -> bool:
    left, right = 0, len(s) - 1
    while left {'<'} right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

Problems: Valid Palindrome (125), Valid Palindrome II (680), Reverse String (344), Two Sum II (167) on sorted char arrays.

Complexity: O(n) time, O(1) space.

Pattern 2: Two pointers — slow and fast

One pointer moves faster or conditionally. Used for removing duplicates, compacting strings.

def remove_duplicates(s: str) -> str:
    if not s:
        return s
    chars = list(s)
    slow = 0
    for fast in range(1, len(chars)):
        if chars[fast] != chars[slow]:
            slow += 1
            chars[slow] = chars[fast]
    return "".join(chars[:slow + 1])

Problems: Remove All Adjacent Duplicates (1047), Backspace String Compare (844).

Pattern 3: Frequency map

Count character occurrences. The foundation for anagram detection, majority element, and group-by problems.

def is_anagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    from collections import Counter
    return Counter(s) == Counter(t)

When to use Counter vs array: Use an array of size 26 when the input is strictly lowercase English (faster). Use Counter/dict for Unicode or mixed character sets.

def is_anagram_array(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    count = [0] * 26
    for ch in s:
        count[ord(ch) - ord('a')] += 1
    for ch in t:
        count[ord(ch) - ord('a')] -= 1
    return all(c == 0 for c in count)

Problems: Valid Anagram (242), Group Anagrams (49), First Unique Character (387), Ransom Note (383).

Complexity: O(n) time, O(1) space (fixed alphabet).

Pattern 4: Sliding window — variable size

Expand right, shrink left when constraint is violated. The workhorse for substring optimization.

def longest_substring_k_distinct(s: str, k: int) -> int:
    from collections import defaultdict
    freq = defaultdict(int)
    left = 0
    max_len = 0

    for right in range(len(s)):
        freq[s[right]] += 1
        while len(freq) > k:
            freq[s[left]] -= 1
            if freq[s[left]] == 0:
                del freq[s[left]]
            left += 1
        max_len = max(max_len, right - left + 1)

    return max_len

Problems: Longest Substring Without Repeating Characters (3), Minimum Window Substring (76), Longest Repeating Character Replacement (424).

Pattern 5: Sliding window — fixed size

Window length is predetermined. Slide and compare.

def find_anagrams(s: str, p: str) -> list:
    from collections import Counter
    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)):
        window[s[i]] += 1
        out = s[i - len(p)]
        window[out] -= 1
        if window[out] == 0:
            del window[out]
        if window == p_count:
            result.append(i - len(p) + 1)

    return result

Problems: Find All Anagrams (438), Permutation in String (567), Substring with Concatenation (30).

Pattern 6: Stack-based processing

Use a stack for matching brackets, decoding nested structures, and removing adjacent duplicates.

def decode_string(s: str) -> str:
    stack = []
    current_str = ""
    current_num = 0

    for ch in s:
        if ch.isdigit():
            current_num = current_num * 10 + int(ch)
        elif ch == '[':
            stack.append((current_str, current_num))
            current_str = ""
            current_num = 0
        elif ch == ']':
            prev_str, num = stack.pop()
            current_str = prev_str + current_str * num
        else:
            current_str += ch

    return current_str

Problems: Valid Parentheses (20), Decode String (394), Remove Duplicate Letters (316), Basic Calculator (224).

Pattern 7: StringBuilder pattern

Build output incrementally using a list. Avoids O(n^2) string concatenation.

def compress(chars: list) -> int:
    write = 0
    read = 0

    while read {'<'} len(chars):
        ch = chars[read]
        count = 0
        while read {'<'} len(chars) and chars[read] == ch:
            read += 1
            count += 1
        chars[write] = ch
        write += 1
        if count > 1:
            for digit in str(count):
                chars[write] = digit
                write += 1

    return write

Problems: String Compression (443), Count and Say (38).

Pattern 8: Reverse tricks

Reverse the whole string, then reverse parts. Or reverse parts first.

def reverse_words(s: str) -> str:
    return " ".join(s.split()[::-1])

Problems: Reverse Words (151), Reverse Words II (186), Rotate String (796).

Pattern 9: Sorting-based grouping

Sort characters to create canonical forms. Two strings are anagrams if and only if their sorted forms are equal.

def group_anagrams(strs: list) -> list:
    from collections import defaultdict
    groups = defaultdict(list)
    for s in strs:
        key = "".join(sorted(s))
        groups[key].append(s)
    return list(groups.values())

Complexity: O(N * L log L) where L is max string length.

Alternative: Use a frequency tuple as key for O(N * L):

def group_anagrams_fast(strs: list) -> list:
    from collections import defaultdict
    groups = defaultdict(list)
    for s in strs:
        count = [0] * 26
        for ch in s:
            count[ord(ch) - ord('a')] += 1
        groups[tuple(count)].append(s)
    return list(groups.values())

Pattern 10: Trie for prefix problems

Build a prefix tree when you need prefix lookup, autocomplete, or word-by-word matching.

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

def search_prefix(root, prefix):
    node = root
    for ch in prefix:
        if ch not in node.children:
            return None
        node = node.children[ch]
    return node

Problems: Implement Trie (208), Word Search II (212), Design Add and Search Words (211).

Pattern 11: Dynamic programming on strings

When the answer depends on subproblems over substrings or subsequences.

def longest_common_subsequence(text1: str, text2: str) -> int:
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    return dp[m][n]

Problems: Edit Distance (72), Longest Common Subsequence (1143), Longest Palindromic Subsequence (516), Word Break (139).

Complexity: Usually O(n^2) or O(n * m).

Pattern 12: String hashing / Rabin-Karp

Rolling hash for O(1) substring comparison.

Problems: Repeated DNA Sequences (187), Longest Duplicate Substring (1044).

Pattern 13: KMP / Z-algorithm

Deterministic linear-time pattern matching with prefix function.

Problems: Implement strStr (28), Repeated Substring Pattern (459), Shortest Palindrome (214).

Pattern 14: Palindrome expansion

Expand from center to find palindromic substrings.

def longest_palindrome_substring(s: str) -> str:
    result = ""

    def expand(left, right):
        nonlocal result
        while left >= 0 and right {'<'} len(s) and s[left] == s[right]:
            if right - left + 1 > len(result):
                result = s[left:right + 1]
            left -= 1
            right += 1

    for i in range(len(s)):
        expand(i, i)      # odd-length palindromes
        expand(i, i + 1)  # even-length palindromes

    return result

Problems: Longest Palindromic Substring (5), Palindromic Substrings (647).

Complexity: O(n^2) time, O(1) space. Manacher’s algorithm does it in O(n).

Pattern 15: Backtracking on strings

Generate all valid combinations by exploring choices recursively.

def generate_parentheses(n: int) -> list:
    result = []

    def backtrack(current, open_count, close_count):
        if len(current) == 2 * n:
            result.append(current)
            return
        if open_count {'<'} n:
            backtrack(current + '(', open_count + 1, close_count)
        if close_count {'<'} open_count:
            backtrack(current + ')', open_count, close_count + 1)

    backtrack("", 0, 0)
    return result

Problems: Generate Parentheses (22), Letter Combinations (17), Palindrome Partitioning (131).

Pattern 16: Greedy string construction

Build the lexicographically smallest or largest string by making locally optimal choices.

def remove_duplicate_letters(s: str) -> str:
    from collections import Counter
    count = Counter(s)
    in_stack = set()
    stack = []

    for ch in s:
        count[ch] -= 1
        if ch in in_stack:
            continue
        while stack and ch {'<'} stack[-1] and count[stack[-1]] > 0:
            in_stack.remove(stack.pop())
        stack.append(ch)
        in_stack.add(ch)

    return "".join(stack)

Problems: Remove Duplicate Letters (316), Smallest Subsequence of Distinct Characters (1081).

Pattern 17: String-to-integer parsing

Manually parse numbers from strings, handling signs, overflow, and whitespace.

Problems: String to Integer atoi (8), Compare Version Numbers (165).

Pattern 18: Encoding and decoding

Design encode/decode functions for string lists, URLs, or compressed formats.

def encode(strs: list) -> str:
    return "".join(f"{len(s)}#{s}" for s in strs)

def decode(s: str) -> list:
    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

Problems: Encode and Decode Strings (271), Serialize and Deserialize Binary Tree (297).

Pattern 19: Character mapping

Map characters between two strings to check isomorphism or pattern matching.

def is_isomorphic(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    s_to_t = {}
    t_to_s = {}
    for cs, ct in zip(s, t):
        if cs in s_to_t and s_to_t[cs] != ct:
            return False
        if ct in t_to_s and t_to_s[ct] != cs:
            return False
        s_to_t[cs] = ct
        t_to_s[ct] = cs
    return True

Problems: Isomorphic Strings (205), Word Pattern (290).

Pattern 20: Bit manipulation on characters

Use XOR, ASCII arithmetic, or bitmasks for character-level operations.

def find_the_difference(s: str, t: str) -> str:
    result = 0
    for ch in s + t:
        result ^= ord(ch)
    return chr(result)

Problems: Find the Difference (389), Single Number on strings.

Decision framework: Trie vs HashMap vs Sorting

This is the question interviewers expect you to reason about:

Scenario	Best Choice	Why
Exact word lookup	HashMap (set)	O(1) average, simplest code
Check all words with prefix	Trie	O(L + results), HashMap needs full scan
Group by content (anagrams)	HashMap + sorted key	O(N * L log L) or O(N * L) with freq key
Autocomplete / suggestions	Trie	Natural prefix traversal
Fuzzy matching (1 char off)	Trie + DFS	Controlled branching
Pattern in text	Rabin-Karp / KMP	O(n + m)
Prefix match in sentence	Trie	Early termination on shortest prefix

Rule of thumb: If the word “prefix” appears in the problem, think Trie. If it says “contains” or “exists”, think HashMap. If it says “sorted” or “lexicographic”, think sorting or Trie.

Common mistakes that cost offers

1. String concatenation in a loop

# WRONG: O(n^2)
result = ""
for ch in data:
    result += ch

# RIGHT: O(n)
parts = []
for ch in data:
    parts.append(ch)
result = "".join(parts)

This is the number one string performance bug. Python creates a new string on every +=.

2. Off-by-one in window calculations

The window [left, right] has length right - left + 1, not right - left. When you shrink by incrementing left, the window becomes one smaller. Double-check with a concrete example.

3. Not handling empty strings

Always check if not s: return ... at the top. Empty strings break indexing, splitting, and frequency counting in subtle ways.

4. Forgetting case sensitivity

“A” and “a” are different characters. If the problem says “ignore case”, normalize with .lower() before processing.

5. Mutating strings in Python

Python strings are immutable. s[0] = 'X' raises TypeError. Convert to a list first: chars = list(s).

6. Not cleaning up zero-count entries in frequency maps

When a character’s count drops to 0, delete it from the dictionary. Otherwise len(freq) reports too many distinct characters, breaking sliding window logic.

freq[ch] -= 1
if freq[ch] == 0:
    del freq[ch]  # CRITICAL

7. Using `==` to compare large strings repeatedly

Each == comparison is O(L). If you compare n substrings of length L, the total is O(n * L). Use hashing for O(1) amortized comparison when n is large.

8. Ignoring Unicode in real interviews

Most interview strings are ASCII, but some problems involve Unicode (emoji, CJK characters). ord() works for all Unicode, but len() can surprise you with surrogate pairs in some languages.

Complexity cheatsheet

Operation	Time	Notes
`s[i]` — index	O(1)
`s[i:j]` — slice	O(j - i)	Creates new string
`s + t` — concat	O(len(s) + len(t))	Creates new string
`s == t` — compare	O(min(len(s), len(t)))
`s.find(t)`	O(n * m) worst	CPython uses mixed Boyer-Moore
`s in t`	O(n * m) worst	Same as find
`s.split()`	O(n)
`"".join(list)`	O(total length)
`sorted(s)`	O(n log n)	Returns list of chars
`Counter(s)`	O(n)
`s.replace(a, b)`	O(n)	Creates new string
`s.lower()` / `s.upper()`	O(n)	Creates new string

Pattern complexity summary

Pattern	Typical Time	Typical Space
Two pointers	O(n)	O(1)
Frequency map	O(n)	O(1) for fixed alphabet
Sliding window	O(n)	O(k) for k distinct
Stack processing	O(n)	O(n)
Trie operations	O(L) per operation	O(N * L) total
DP on strings	O(n * m)	O(n * m), often reducible
Palindrome expansion	O(n^2)	O(1)
Backtracking	O(2^n) or O(n!)	O(n) recursion depth
String hashing	O(n)	O(n)
Sort-based grouping	O(N * L log L)	O(N * L)

Interview strategy

Step 1: Classify the problem (30 seconds)

Ask yourself these questions in order:

Is it about a contiguous substring? -> Sliding window or two pointers.
Is it about permutations/anagrams? -> Frequency map.
Does it involve prefixes? -> Trie.
Is it about subsequences? -> DP.
Does it have nested structure (brackets, encoding)? -> Stack.
Is it asking for all valid combinations? -> Backtracking.

Step 2: Clarify constraints (1 minute)

String length (determines if O(n^2) is acceptable).
Character set (lowercase only? ASCII? Unicode?).
Case sensitivity.
What to return (boolean, string, list of indices).
Edge cases: empty string, single character, all same characters.

Step 3: State your approach (1 minute)

Name the pattern: “I will use a sliding window with a frequency map.” State the expected complexity. Get confirmation before coding.

Step 4: Code and test (15-20 minutes)

Write clean code with descriptive variable names. Test with the given example and at least one edge case. Walk through your code line by line.

Step 5: Optimize if asked (5 minutes)

Common follow-ups:

“Can you do it in O(1) space?” -> Two pointers instead of hash map.
“Can you do it in one pass?” -> Sliding window instead of two-pass.
“What if the string is very long?” -> Streaming/rolling hash.

Practice roadmap

Week 1: Foundations

Reverse String (344) — two pointers
Valid Anagram (242) — frequency map
First Unique Character (387) — frequency map
Valid Palindrome (125) — two pointers + cleanup

Week 2: Sliding window

Longest Substring Without Repeating Characters (3)
Minimum Window Substring (76)
Find All Anagrams (438)
Permutation in String (567)

Week 3: Stack and DP

Valid Parentheses (20)
Decode String (394)
Longest Palindromic Substring (5)
Edit Distance (72)

Week 4: Advanced

Word Break (139)
Group Anagrams (49)
Implement Trie (208)
Word Search II (212)
Longest Duplicate Substring (1044)
Shortest Palindrome (214)

Complete this roadmap and you will be ready for any string question an interviewer can throw at you. The patterns repeat — once you recognize them, the solutions follow naturally.

Final thoughts

String problems are not about memorizing solutions. They are about recognizing which of these 20 patterns applies, then writing clean code that handles edge cases. The candidates who get offers are not the ones who have seen every problem — they are the ones who can identify the pattern in 30 seconds and implement it without bugs in 15 minutes.

Study the patterns. Practice the templates. Trust the process.