Top 12 String Interview Problems: Patterns and What Each Teaches

You can grind 80 string interview problems and still feel like you've seen nothing twice. That's not a skill gap. That's a pattern-recognition gap. There are seven structural moves in the entire string category. These 12 problems cover all of them.

Learn the patterns below and 90% of string problems collapse into familiar ground.

Pattern	Core idea
Frequency map	Count characters, compare counts
Two pointers	Walk from both ends inward
Sliding window	Expand right, shrink left on condition
Expand around center	Palindromes radiate outward from every position
Dynamic programming	Substring answers depend on smaller substring answers
Stack	Last-in-first-out for matching and nesting
Pattern matching	Never back up the text pointer

Count First, Ask Questions Later

1. Valid Anagram (LC 242, Easy)

Two strings are anagrams if they contain the same characters with the same counts. The naive move is sorting both strings and comparing. O(n log n). Interviewer smiles politely.

The O(n) move: count one string, decrement against the other.

def isAnagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    count = {}
    for c in s:
        count[c] = count.get(c, 0) + 1
    for c in t:
        count[c] = count.get(c, 0) - 1
        if count[c] < 0:
            return False
    return True

This is the building block for the entire anagram family. Every problem involving "same characters, different order" reduces to this exact frequency comparison. Memorize the shape.

2. Group Anagrams (LC 49, Medium)

Group anagrams together. The trick: any two anagrams of each other must produce the same canonical key. Sorted characters are a perfect fingerprint.

from collections import defaultdict

def groupAnagrams(strs: list[str]) -> list[list[str]]:
    groups = defaultdict(list)
    for word in strs:
        key = tuple(sorted(word))
        groups[key].append(word)
    return list(groups.values())

Sorted characters produce a unique fingerprint for an anagram group. The tuple is hashable; a list is not. That's the common first-attempt bug, and it fails silently enough to waste ten minutes.

Walk From Both Ends

3. Valid Palindrome (LC 125, Easy)

Walk two pointers from each end, skip non-alphanumeric characters, compare what's left. Simple enough that candidates blow it by forgetting the guard on the inner loops.

def isPalindrome(s: str) -> bool:
    lo, hi = 0, len(s) - 1
    while lo < hi:
        while lo < hi and not s[lo].isalnum():
            lo += 1
        while lo < hi and not s[hi].isalnum():
            hi -= 1
        if s[lo].lower() != s[hi].lower():
            return False
        lo += 1
        hi -= 1
    return True

Both inner while loops need the lo < hi guard, otherwise you can cross the pointers and read garbage. That's where candidates stumble. Every time.

Expand Right, Shrink Left

4. Longest Substring Without Repeating Characters (LC 3, Medium)

This is everyone's first real sliding window problem. The window expands right on every step and shrinks left whenever a duplicate enters.

def lengthOfLongestSubstring(s: str) -> int:
    seen = {}
    lo = 0
    best = 0
    for hi, c in enumerate(s):
        if c in seen and seen[c] >= lo:
            lo = seen[c] + 1
        seen[c] = hi
        best = max(best, hi - lo + 1)
    return best

The key line is seen[c] >= lo. If the previous occurrence is to the left of the current window start, it doesn't matter. Without that check you'll shrink the window on characters that re-entered from outside the window, which produces wrong answers that look subtly plausible until your example has two as and you stare at it for four minutes.

5. Find All Anagrams in a String (LC 438, Medium)

Fixed-length window of size len(p), sliding across s. Compare frequency maps at each position.

from collections import Counter

def findAnagrams(s: str, p: str) -> list[int]:
    need = Counter(p)
    window = Counter(s[:len(p)])
    result = []
    if window == need:
        result.append(0)
    for i in range(len(p), len(s)):
        c_in = s[i]
        c_out = s[i - len(p)]
        window[c_in] += 1
        window[c_out] -= 1
        if window[c_out] == 0:
            del window[c_out]
        if window == need:
            result.append(i - len(p) + 1)
    return result

You slide one character in and one out at each step. Deleting zero-count keys keeps the Counter comparison correct. This pattern also appears in exactly-k-distinct-characters problems. The delete step is the one most candidates skip.

6. Minimum Window Substring (LC 76, Hard)

This is the problem that filters out people who think they understand sliding window. The canonical hard sliding window. Expand right until you have all required characters, then shrink left as far as possible, record the window, then expand again.

from collections import Counter

def minWindow(s: str, t: str) -> str:
    need = Counter(t)
    have, required = 0, len(need)
    window = {}
    lo, best_lo, best_len = 0, 0, float("inf")

    for hi, c in enumerate(s):
        window[c] = window.get(c, 0) + 1
        if c in need and window[c] == need[c]:
            have += 1
        while have == required:
            if hi - lo + 1 < best_len:
                best_len = hi - lo + 1
                best_lo = lo
            left_c = s[lo]
            window[left_c] -= 1
            if left_c in need and window[left_c] < need[left_c]:
                have -= 1
            lo += 1

    return s[best_lo:best_lo + best_len] if best_len != float("inf") else ""

The have counter tracks how many distinct characters have met their required count. You increment it only when a character's count exactly hits the requirement. That keeps the while condition cheap and correct. The common wrong version checks window == need on every step, which is O(k) per step instead of O(1).

Every Position Is a Palindrome Candidate

7. Longest Palindromic Substring (LC 5, Medium)

Most people try DP first. It works, but the expand-around-center approach is shorter to write and easier to explain under pressure. Treat every character and every gap between characters as a potential palindrome center. Expand outward while the flanking characters match.

def longestPalindrome(s: str) -> str:
    def expand(lo: int, hi: int) -> str:
        while lo >= 0 and hi < len(s) and s[lo] == s[hi]:
            lo -= 1
            hi += 1
        return s[lo + 1:hi]

    best = ""
    for i in range(len(s)):
        odd = expand(i, i)
        even = expand(i, i + 1)
        if len(odd) > len(best):
            best = odd
        if len(even) > len(best):
            best = even
    return best

There are 2n - 1 centers in a string of length n: n odd centers and n - 1 even centers. Manacher's runs in O(n) if you need it, but the expand-around-center O(n²) solution is what interviewers expect. Save Manacher's for the follow-up.

8. Palindromic Substrings (LC 647, Medium)

Count all palindromic substrings. Same expand-around-center, but count every successful expansion instead of tracking the longest. If you've solved LC 5, this should take three minutes.

def countSubstrings(s: str) -> int:
    count = 0
    def expand(lo: int, hi: int):
        nonlocal count
        while lo >= 0 and hi < len(s) and s[lo] == s[hi]:
            count += 1
            lo -= 1
            hi += 1

    for i in range(len(s)):
        expand(i, i)
        expand(i, i + 1)
    return count

The expand logic is identical. The only change is what you do when an expansion succeeds. LC 5: update the best. LC 647: increment the count. Same skeleton, different payload.

When the Substring Needs a Smaller Substring

9. Word Break (LC 139, Medium)

Can the string be segmented into dictionary words? The brute-force recursive approach will time out spectacularly. dp[i] is true if s[0:i] can be fully segmented.

def wordBreak(s: str, wordDict: list[str]) -> bool:
    words = set(wordDict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in words:
                dp[i] = True
                break
    return dp[n]

The state is a prefix boundary, not an index pair. dp[i] answers "can I get to position i using only dictionary words?" This framing reappears in palindrome partitioning and sentence reconstruction. The set lookup keeps each inner iteration at O(substring length), not O(dict size).

10. Longest Common Subsequence (LC 1143, Medium)

The foundational two-sequence DP problem. dp[i][j] is the LCS length of text1[:i] and text2[:j].

def longestCommonSubsequence(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]

The recurrence behind edit distance, longest common substring, and shortest common supersequence is this same table with slightly different recurrences. Every two-string DP problem is a variant of this. Learn the indices once and you'll never re-derive them.

When Order of Arrival Matters

11. Longest Valid Parentheses (LC 32, Hard)

The naive O(n²) approach scans every substring and checks if it's valid. It works. It also makes your interviewer quietly update the hire decision. Here's the O(n) stack approach.

def longestValidParentheses(s: str) -> int:
    stack = [-1]
    best = 0
    for i, c in enumerate(s):
        if c == '(':
            stack.append(i)
        else:
            stack.pop()
            if not stack:
                stack.append(i)
            else:
                best = max(best, i - stack[-1])
    return best

Store indices on the stack, not characters. The unmatched ) becomes the new base boundary. The sentinel -1 at initialization handles the edge case where the first character is ). This technique generalizes to any problem that needs to measure spans of matched structure.

Stop Restarting from Zero

12. Find the Index of First Occurrence (LC 28, Easy)

Classified as Easy. The naive O(nm) solution passes all test cases. But if your interviewer asks "can you do better?", and they will, the answer is KMP. It runs in O(n + m) by never backing up the text pointer.

def strStr(haystack: str, needle: str) -> int:
    m = len(needle)
    lps = [0] * m
    j = 0
    for i in range(1, m):
        while j > 0 and needle[i] != needle[j]:
            j = lps[j - 1]
        if needle[i] == needle[j]:
            j += 1
        lps[i] = j

    j = 0
    for i, c in enumerate(haystack):
        while j > 0 and c != needle[j]:
            j = lps[j - 1]
        if c == needle[j]:
            j += 1
        if j == m:
            return i - m + 1
    return -1

The failure function (lps array) encodes the longest prefix of the pattern that is also a suffix. After a mismatch, you restart from the furthest position that still matches a prefix, not from zero. The text pointer i never moves backward. That's the whole insight, and it took Knuth, Morris, and Pratt to formalize it.

KMP is one of those algorithms where the code looks like someone fell asleep on the keyboard. The best way to internalize it is to trace through a short example by hand, watching j jump backward through the lps array. Do that once and the rest clicks.

String Interview Problem Patterns, Distilled

Anagram problems reduce to frequency maps. Sorted characters or count tuples are your canonical key.
Every sliding window has the same skeleton: expand right, check condition, shrink left. The condition and the shrink trigger are the only moving parts.
Palindrome problems split into find-longest (track best) and count-all (increment per expansion). The expand logic is identical in both.
Two-sequence DP tables have three cases: characters match (inherit diagonal), characters differ (take max of left or up).
Stack problems involving spans or matching almost always store indices, not values.
Naive pattern matching is O(nm). If the interviewer says "can you do better," KMP is the answer. Learn how the failure function is built before the loop.

If you want to see how these patterns hold up under interview pressure, the sliding window guide breaks down the expand-shrink mechanics in detail. For the DP problems, the dynamic programming framework covers state identification and recurrence writing before you touch code.

Knowing the patterns is half the preparation. The other half is narrating your thinking in real time under pressure. SpaceComplexity runs voice-based mock interviews with rubric scoring across communication, problem-solving, code quality, and optimization so you can drill the string patterns and the spoken performance simultaneously.

Once these 12 are solid, the string internals guide covers why string concatenation in a loop is O(n²) and why that matters when you analyze your solution out loud.