String Problems That Meta and Google Actually Ask — Curated FAANG Set

Problem and Topic Statement#

This guide curates the string problems that appear repeatedly in Meta and Google interview loops, grouped by the underlying pattern. The list is built from public reports, Glassdoor leaks, recurrent leetcode-tagged questions, and ICPC training tracks. Each entry names the problem, the FAANG company most associated with it, and the canonical pattern that solves it.

Coverage by company tag (approximate, derived from public sources):

• Meta: Minimum Window Substring, Group Anagrams, Valid Palindrome II, Add Strings, Multiply Strings, Longest Substring Without Repeating Characters.
• Google: Longest Palindromic Substring, Word Break, Word Break II, Decode Ways, Edit Distance, Regular Expression Matching, Wildcard Matching.
• Amazon: String Compression, Most Common Word, Reorganise String, Reverse Words in a String III.
• Apple, Bloomberg, Microsoft: Implement strStr (KMP or Z), Repeated Substring Pattern, Roman to Integer.

Master the patterns rather than the individual problems and you cover roughly 80 percent of string-heavy FAANG screens.

Why This Topic Matters#

Interview prep optimisation is a real skill. Spending two hundred hours grinding random LeetCode strings is far less effective than spending fifty hours mastering eight patterns and the twenty-five problems that reify them. The patterns covered below — sliding window, KMP, two-pointer, dynamic programming, trie, and rolling hash — repeat across hundreds of LeetCode problems.

Beyond passing interviews, these patterns matter in production. Sliding window powers anomaly detection in time-series streams. KMP and rolling hash power log search and grep. Trie powers autocomplete and IDE token completion. Edit distance powers spell checkers and DNA alignment. Each problem in this list is a toy version of a real engineering tool.

The leverage of curated practice is enormous. By concentrating on patterns rather than memorisation, you can pivot to a new problem variant within minutes during the interview itself. Interviewers grade for adaptability — and pattern fluency is exactly what produces it.

The Core Insight — Pattern Map#

Roughly six patterns cover the bulk of FAANG string problems.

Sliding window. Maintain a left and right pointer plus a state (counter, frequency vector, mismatch count). Expand right; shrink left when constraint is violated. Solves Minimum Window Substring (LC 76), Longest Substring Without Repeating Characters (LC 3), Permutation in String (LC 567), Find All Anagrams (LC 438).

Two-pointer / palindrome check. Pointers walk inward. Solves Valid Palindrome (LC 125), Valid Palindrome II (LC 680), Reverse String (LC 344), Reverse Words in a String (LC 151).

KMP / failure function. When pattern matching is the core operation. Solves strStr (LC 28), Repeated Substring Pattern (LC 459), Shortest Palindrome (LC 214), periodic substring detection.

Trie. Dictionary lookups by prefix. Solves Implement Trie (LC 208), Word Search II (LC 212), Replace Words (LC 648), Stream of Characters (LC 1032).

String DP. 2D table indexed by prefixes of two strings. Solves Edit Distance (LC 72), Longest Common Subsequence (LC 1143), Distinct Subsequences (LC 115), Regular Expression Matching (LC 10), Wildcard Matching (LC 44), Word Break (LC 139), Decode Ways (LC 91).

Rolling hash / hashing. Constant-time substring comparison. Solves Repeated DNA Sequences (LC 187), Longest Duplicate Substring (LC 1044), Distinct Echo Substrings (LC 1316).

Big-int string arithmetic. Add Strings (LC 415), Multiply Strings (LC 43), and Add Binary (LC 67). Implement integer arithmetic on character arrays digit by digit; emulates how Python handles arbitrary-precision integers internally.

Visual Dry Run / Worked Example#

Minimum Window Substring (Meta). Find the smallest window in s containing all characters of t (with multiplicity).

Pattern: sliding window with two frequency arrays — need (target counts from t) and have (current window counts). Track matches = number of distinct characters where have[ch] >= need[ch]. Expand right adding characters; when matches == required, shrink left as long as the window remains valid; record minimum.

s = "ADOBECODEBANC", t = "ABC". Required = 3.

Walk:

expand A: have A=1, matches=1
expand D, O, B: matches stays at 1 (B contributes), then 2
expand E, C: matches=3 -> window "ADOBEC" valid; record length 6
shrink A: matches drops to 2; stop shrinking
expand O, D, E, B: matches=3 again
... continue until window "BANC" length 4 found

Final answer: BANC.

Edit Distance (Google). s1 = "horse", s2 = "ros". Build dp[i][j] = edit distance between s1[:i] and s2[:j].

       ""  r  o  s
   "" [0, 1, 2, 3]
   h  [1, 1, 2, 3]
   o  [2, 2, 1, 2]
   r  [3, 2, 2, 2]
   s  [4, 3, 3, 2]
   e  [5, 4, 4, 3]

Answer: dp[5][3] = 3.

Solution (Optimal)#

Minimum Window Substring (Python)#

from collections import Counter
 
def minWindow(s, t):
    if not s or not t:
        return ""
    need = Counter(t)
    required = len(need)
    have = {}
    matches = 0
    left = 0
    best = (float('inf'), 0, 0)
    for right, ch in enumerate(s):
        have[ch] = have.get(ch, 0) + 1
        if ch in need and have[ch] == need[ch]:
            matches += 1
        while matches == required:
            if right - left + 1 < best[0]:
                best = (right - left + 1, left, right)
            lch = s[left]
            have[lch] -= 1
            if lch in need and have[lch] < need[lch]:
                matches -= 1
            left += 1
    return "" if best[0] == float('inf') else s[best[1]:best[2] + 1]

Edit Distance (Python)#

def minDistance(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

Word Break (Python)#

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

JavaScript — Edit Distance#

function minDistance(s1, s2) {
  const m = s1.length, n = s2.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
  for (let i = 0; i <= m; i++) dp[i][0] = i;
  for (let j = 0; j <= n; j++) dp[0][j] = j;
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (s1[i - 1] === s2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
      else dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]);
    }
  }
  return dp[m][n];
}

Complexity for each: as in their canonical writeups (sliding window O(n+m), edit distance O(n*m), word break O(n * max_len)).

Common Mistakes#

• Confusing sliding window with two-pointer. Sliding window is for contiguous substrings with monotone shrink; two-pointer is for non-contiguous matching like palindrome checks.
• Mismanaging the matches counter in minimum window substring. The increment must happen exactly when have transitions from need-1 to need; the decrement must mirror it.
• Forgetting space optimisation in DP problems. Edit distance's 2D table can be reduced to two rows or one row with care.
• Brute-forcing word break. Without memoisation it is exponential.
• Implementing add-strings without zero-padding the shorter string. Easier to align indices from the right.

Interview Tips#

State the pattern up front. Start every problem with "this is a sliding window" or "this looks like a 2D string DP". Interviewers grade for pattern fluency in the first two minutes.

For Meta-style problems, walk through one example slowly. Meta interviewers prefer crisp, careful, slightly-deeper answers over speed.

For Google-style problems, articulate complexity in O() before coding. Google interviewers grade for analytical clarity; vague hand-waving sinks scores.

For Amazon and Microsoft, focus on edge cases — empty input, single character, very long input, Unicode. Amazon's bar is bug-free production-quality code.

When stuck, return to the pattern. If you cannot solve a string problem, stating "this looks like edit distance and I would set up dp[i][j] as ..." earns partial credit even when the solution is incomplete.

Follow-up Questions#

1. Optimise edit distance space. Two rows or one row plus a saved diagonal cell.
2. Word break with the actual partition list (LC 140). Switch to memoised DFS that returns lists of strings.
3. Decode Ways with negative numbers / leading zeros. Add edge-case checks; the recurrence is the same.
4. Multiple patterns simultaneously. Aho-Corasick automaton; will be covered in the next blog.
5. Streaming substring matching. KMP works directly on streams; suffix automaton supports incremental insertion.

Key Takeaways#

• A handful of patterns cover the bulk of FAANG string problems; mastering eight patterns is more valuable than memorising two hundred problems.
• Sliding window dominates "find the substring with property X" questions across Meta and Google.
• Two-pointer dominates palindrome and reversal questions.
• KMP and rolling hash dominate pattern matching, periodicity, and substring uniqueness questions.
• Trie dominates dictionary-based questions including autocomplete, prefix search, and Word Search II.
• 2D string DP dominates transformation questions including edit distance, LCS, regex, wildcard, decode ways, and word break.
• Stating the pattern out loud at minute one of the interview is the highest-leverage thing you can do; interviewers grade for it before they grade your code.