String Problems: The Patterns Behind Every Interview Question

String problems are everywhere in coding interviews. They're popular because strings are familiar, the problem statements are easy to understand, and the solutions test a wide range of techniques — hashing, two pointers, sliding window, dynamic programming, and more.

The good news: string problems aren't as varied as they seem. Most of them use one of a handful of patterns. Learn those patterns and you'll handle almost anything they throw at you.

When You'll See String Problems

Practically every coding interview includes at least one string problem. They show up as warm-up questions (valid palindrome, reverse a string), as medium-difficulty problems (longest substring without repeating characters, group anagrams), and as hard problems (minimum window substring, regex matching).

They're also common in phone screens because they're easy to explain and the code is usually short enough to write in a shared editor.

Pattern 1: Frequency Counting

The most fundamental string pattern. Count how often each character appears and use that information to answer questions.

Tool: A hash map (dictionary in Python, or a fixed-size array of length 26 for lowercase English letters).

Problem: Valid Anagram

Given two strings, determine if one is an anagram of the other.

def is_anagram(s, t):
    if len(s) != len(t):
        return False

freq = {}
    for c in s:
        freq[c] = freq.get(c, 0) + 1
    for c in t:
        freq[c] = freq.get(c, 0) - 1

return all(v == 0 for v in freq.values())

Or more concisely using Counter:

from collections import Counter

def is_anagram(s, t):
    return Counter(s) == Counter(t)

O(n) time, O(1) space (at most 26 unique characters for lowercase English).

Problem: Group Anagrams

Given a list of strings, group the anagrams together.

from collections import defaultdict

def group_anagrams(strs):
    groups = defaultdict(list)
    for s in strs:
        key = tuple(sorted(s))  # or use a frequency tuple
        groups[key].append(s)
    return list(groups.values())

The key insight: two strings are anagrams if and only if they have the same sorted form (or the same character frequency tuple). Use that as a hash map key.

For better performance, use a frequency tuple instead of sorting:

def group_anagrams(strs):
    groups = defaultdict(list)
    for s in strs:
        freq = [0] * 26
        for c in s:
            freq[ord(c) - ord('a')] += 1
        groups[tuple(freq)].append(s)
    return list(groups.values())

This is O(n k) where k is the max string length, versus O(n k log k) with sorting.

Problem: First Unique Character

Given a string, find the first character that doesn't repeat.

def first_unique_char(s):
    freq = {}
    for c in s:
        freq[c] = freq.get(c, 0) + 1

for i, c in enumerate(s):
        if freq[c] == 1:
            return i

return -1

Two passes: first count frequencies, then find the first character with count 1.

Problem: Ransom Note

Can you construct the ransom note string from the characters in the magazine string?

from collections import Counter

def can_construct(ransom_note, magazine):
    mag_freq = Counter(magazine)
    for c in ransom_note:
        if mag_freq[c] <= 0:
            return False
        mag_freq[c] -= 1
    return True

When to Use Frequency Counting

Anytime the problem involves character occurrence, duplicates, or comparing character compositions between strings. It's the first thing you should consider for string problems.

Pattern 2: Palindrome Patterns

Palindromes are strings that read the same forward and backward. They come up constantly in interviews, and there are a few standard approaches.

Approach 1: Two Pointers (Verification)

To check if a string is a palindrome, use two pointers moving inward from the ends:

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

Problem: Valid Palindrome (with non-alphanumeric characters)

def is_palindrome_clean(s):
    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

Problem: Valid Palindrome II (Can Remove One Character)

Given a string, determine if it can become a palindrome by removing at most one character.

def valid_palindrome(s):
    def check(left, right):
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True

left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            # try removing left char or right char
            return check(left + 1, right) or check(left, right - 1)
        left += 1
        right -= 1
    return True

Approach 2: Expand Around Center (Finding Palindromic Substrings)

To find all palindromic substrings, or the longest one, expand from each possible center:

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

result = ""
    for i in range(len(s)):
        # odd length palindromes
        odd = expand(i, i)
        if len(odd) > len(result):
            result = odd
        # even length palindromes
        even = expand(i, i + 1)
        if len(even) > len(result):
            result = even

return result

O(n^2) time, O(1) space (excluding the result). There are n centers for odd-length palindromes and n-1 for even-length, and each expansion takes O(n) in the worst case.

Problem: Palindromic Substrings (Count)

How many palindromic substrings exist in the string?

def count_palindromes(s):
    count = 0
    for i in range(len(s)):
        # odd length
        left, right = i, i
        while left >= 0 and right < len(s) and s[left] == s[right]:
            count += 1
            left -= 1
            right += 1
        # even length
        left, right = i, i + 1
        while left >= 0 and right < len(s) and s[left] == s[right]:
            count += 1
            left -= 1
            right += 1
    return count

Same expand-around-center technique, just counting instead of tracking the longest.

Pattern 3: Sliding Window on Strings

The sliding window technique is incredibly powerful for string problems involving substrings with some constraint.

Problem: Longest Substring Without Repeating Characters

def length_of_longest_substring(s):
    char_set = set()
    left = 0
    max_len = 0

for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        max_len = max(max_len, right - left + 1)

return max_len

Variable-size window that expands to the right and shrinks from the left whenever a duplicate is found.

Problem: Minimum Window Substring

Given strings s and t, find the smallest substring of s that contains all characters of t. This is considered a hard problem, but it's a direct application of the sliding window template.

from collections import Counter

def min_window(s, t):
    if not t or not s:
        return ""

target = Counter(t)
    required = len(target)     # number of unique chars in t that must be present
    formed = 0                 # number of unique chars in current window matching target
    window_counts = {}

best_len = float('inf')
    best_left = 0
    left = 0

for right in range(len(s)):
        char = s[right]
        window_counts[char] = window_counts.get(char, 0) + 1

if char in target and window_counts[char] == target[char]:
            formed += 1

while formed == required:
            # update best
            if right - left + 1 < best_len:
                best_len = right - left + 1
                best_left = left

# shrink
            left_char = s[left]
            window_counts[left_char] -= 1
            if left_char in target and window_counts[left_char] < target[left_char]:
                formed -= 1
            left += 1

return "" if best_len == float('inf') else s[best_left:best_left + best_len]

The formed counter tracks how many characters have met their frequency requirement. When formed == required, the window contains all characters of t, so we try to shrink it.

Problem: Find All Anagrams in a String

Given strings s and p, find all start indices of p's anagrams in s. This is a fixed-size sliding window of length len(p).

from collections import Counter

def find_anagrams(s, p):
    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 new char
        window[s[i]] += 1
        # remove old char
        old = s[i - len(p)]
        window[old] -= 1
        if window[old] == 0:
            del window[old]

if window == p_count:
            result.append(i - len(p) + 1)

return result

Problem: Longest Substring with At Most K Distinct Characters

def longest_k_distinct(s, k):
    freq = {}
    left = 0
    max_len = 0

for right in range(len(s)):
        freq[s[right]] = freq.get(s[right], 0) + 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

When to Use Sliding Window on Strings

The problem asks about a substring (contiguous) with some constraint (unique characters, contains all characters of another string, at most K distinct characters). The constraint can be checked incrementally as the window expands and shrinks.

Pattern 4: Two Pointers on Strings

Beyond palindromes, two pointers solve several string problems efficiently.

Problem: Is Subsequence

Given strings s and t, is s a subsequence of t?

def is_subsequence(s, t):
    i, j = 0, 0
    while i < len(s) and j < len(t):
        if s[i] == t[j]:
            i += 1
        j += 1
    return i == len(s)

O(n) with two pointers — much cleaner than trying to use dynamic programming for this.

Problem: Backspace String Compare

Given two strings with '#' representing backspace, compare them.

def backspace_compare(s, t):
    def next_valid(string, index):
        skip = 0
        while index >= 0:
            if string[index] == '#':
                skip += 1
            elif skip > 0:
                skip -= 1
            else:
                return index
            index -= 1
        return -1

i = next_valid(s, len(s) - 1)
    j = next_valid(t, len(t) - 1)

while i >= 0 and j >= 0:
        if s[i] != t[j]:
            return False
        i = next_valid(s, i - 1)
        j = next_valid(t, j - 1)

return i == j  # both should be -1

O(n) time, O(1) space — compare from right to left, skipping backspaced characters.

Pattern 5: String Building

Some problems require building or transforming a string. The key in Python: don't concatenate strings in a loop (it's O(n) per concatenation due to immutability). Build a list and join at the end.

Problem: String Compression

Compress "aabcccccaaa" to "a2b1c5a3".

def compress(s):
    result = []
    count = 1

for i in range(1, len(s) + 1):
        if i < len(s) and s[i] == s[i-1]:
            count += 1
        else:
            result.append(s[i-1])
            result.append(str(count))
            count = 1

compressed = ''.join(result)
    return compressed if len(compressed) < len(s) else s

Problem: Decode String

Given "3[a2[c]]", decode to "accaccacc". Use a stack for nested structures.

def decode_string(s):
    stack = []
    current_string = []
    current_num = 0

for char in s:
        if char.isdigit():
            current_num = current_num * 10 + int(char)
        elif char == '[':
            stack.append((''.join(current_string), current_num))
            current_string = []
            current_num = 0
        elif char == ']':
            prev_string, num = stack.pop()
            current_string = list(prev_string + ''.join(current_string) * num)
        else:
            current_string.append(char)

return ''.join(current_string)

The stack stores the state before each opening bracket: the string built so far and the repeat count. When we hit a closing bracket, we pop and combine.

Problem: Reverse Words in a String

def reverse_words(s):
    words = s.split()
    return ' '.join(reversed(words))

In an interview, they might ask you to do it in-place (which is more relevant in languages with mutable strings like C). The approach: reverse the entire string, then reverse each word individually.

Common Mistakes

Using string concatenation in a loop. In Python, result += char in a loop is O(n^2) total because strings are immutable. Use a list and ''.join(). Forgetting about Unicode / case sensitivity. Always clarify with the interviewer: are we dealing with only lowercase English? ASCII? Unicode? Do uppercase and lowercase count as the same character? Off-by-one in substring slicing. Python's s[i:j] includes index i but excludes j. Be precise about boundaries, especially in sliding window problems. Not handling empty strings. Check for empty input at the start. Many string functions behave unexpectedly on empty strings. Sorting when hashing would work. Sorting a string to check for anagrams is O(k log k). Using a frequency count is O(k). Both work in interviews, but mentioning the optimization shows awareness.

Practice Problems

Frequency counting: Valid Anagram, Group Anagrams, First Unique Character, Ransom Note, Sort Characters by Frequency Palindromes: Valid Palindrome, Valid Palindrome II, Longest Palindromic Substring, Palindromic Substrings, Palindrome Pairs Sliding window: Longest Substring Without Repeating Characters, Minimum Window Substring, Find All Anagrams, Longest Repeating Character Replacement, Permutation in String Two pointers: Is Subsequence, Backspace String Compare, Longest Common Prefix String building: String Compression, Decode String, Reverse Words, Integer to Roman, Simplify Path

Work through these patterns on CodeUp — once you can recognize which pattern a string problem uses, the solution writes itself.