String Interview Problems: Patterns, Tricks and the Questions That Keep Coming Back

Strings appear in nearly every online assessment and first-round coding interview because they test basic data structure fluency and careful edge-case handling at once. Most string questions are not about exotic algorithms. They are about seeing that "is this a permutation of that" is a frequency comparison, that "longest substring with a property" is a sliding window, and that nested brackets mean a stack.

This guide groups string interview problems by pattern, solves the representative problem for each in Python and Java, and ends with a practice list and the pitfalls interviewers watch for. Many techniques carry over from arrays, so if those are new, start with array interview patterns.

Why String Problems Are Different From Array Problems

The alphabet is small. If input is lowercase English letters, a frequency table is 26 integers: O(1) space, faster than any hashmap. Always ask: "lowercase only? ASCII? Unicode?" The answer decides between int[26], int[128] and a map.

Strings are immutable in Java, Python, JavaScript and C#. Every "modification" creates a new string, so naive concatenation in a loop is quadratic. C++ std::string is mutable, which changes some in-place answers.

Comparisons cost O(length). Using a string as a hashmap key costs O(k) to hash, and comparing two strings is O(k). Complexity statements like "sorting n strings of length k is O(n·k·log n)" earn credit.

Edge cases multiply: empty string, single character, all same characters, spaces, mixed case, digits, and non-ASCII input.

String Operations Cheat Sheet: Java, Python, C++

Pattern 1: Frequency Maps (Counting Characters)

Signal: the question is about which characters appear and how often, not their order: anagram checks, ransom note, first unique character, "can you rearrange to form X".

Representative problem: Valid Anagram (LeetCode 242). Increment for s, decrement for t, and require all zeros.

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;
    int[] count = new int[26];
    for (int i = 0; i < s.length(); i++) {
        count[s.charAt(i) - 'a']++;
        count[t.charAt(i) - 'a']--;
    }
    for (int c : count) if (c != 0) return false;
    return true;
}

from collections import Counter

def is_anagram(s: str, t: str) -> bool:
    return len(s) == len(t) and Counter(s) == Counter(t)

def first_unique_char(s: str) -> int:
    freq = Counter(s)
    for i, ch in enumerate(s):
        if freq[ch] == 1:
            return i
    return -1

O(n) time and O(1) space for a fixed alphabet. The follow-up "what if the input contains Unicode?" is answered by switching to a hashmap; in Java, also note that a char is a UTF-16 code unit, so characters outside the Basic Multilingual Plane (most emoji) span two chars and need codePoints().

Two more members of this family: Ransom Note (count the magazine, consume for the note) and Isomorphic Strings (two maps, s-to-t and t-to-s, because the mapping must be one-to-one; a single map wrongly accepts "ab" to "aa").

Pattern 2: Grouping Anagrams With a Canonical Key

Signal: group or deduplicate strings that are "equivalent" under some transformation. Compute a canonical key per string and bucket by it.

Representative problem: Group Anagrams (LeetCode 49). Two key choices:

• Sorted string as key: O(k log k) per word.
• Count signature (26 counts) as key: O(k) per word, better for long words.

from collections import defaultdict

def group_anagrams(words):
    groups = defaultdict(list)
    for w in words:
        key = [0] * 26
        for ch in w:
            key[ord(ch) - ord('a')] += 1
        groups[tuple(key)].append(w)       # lists are unhashable; tuples are fine
    return list(groups.values())

public List<List<String>> groupAnagrams(String[] words) {
    Map<String, List<String>> groups = new HashMap<>();
    for (String w : words) {
        char[] a = w.toCharArray();
        Arrays.sort(a);
        groups.computeIfAbsent(new String(a), k -> new ArrayList<>()).add(w);
    }
    return new ArrayList<>(groups.values());
}

Complexity: O(n·k log k) with sorted keys, O(n·k) with count keys, where n is the number of words and k the maximum length. The same canonical-key idea solves "group shifted strings" (key = differences between consecutive characters mod 26).

Pattern 3: Sliding Window on Strings

Signal: longest or shortest substring with a property, or "find all positions where a permutation of p appears". Substring means contiguous, which is exactly what a window models.

Fixed window: Find All Anagrams in a String (LeetCode 438)

public List<Integer> findAnagrams(String s, String p) {
    List<Integer> res = new ArrayList<>();
    int k = p.length();
    if (k > s.length()) return res;
    int[] need = new int[26], win = new int[26];
    for (char c : p.toCharArray()) need[c - 'a']++;
    for (int i = 0; i < s.length(); i++) {
        win[s.charAt(i) - 'a']++;                       // char entering
        if (i >= k) win[s.charAt(i - k) - 'a']--;       // char leaving
        if (i >= k - 1 && Arrays.equals(win, need)) res.add(i - k + 1);
    }
    return res;
}

O(26·n), which is O(n). To remove the 26 factor, keep a matches counter of how many letters currently have equal counts and update it only for the entering and leaving characters. Permutation in String (567) is the same code returning a boolean.

Variable window: Longest Substring Without Repeating Characters

def length_of_longest_substring(s: str) -> int:
    last = {}                  # char -> last index seen
    left = best = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1          # jump past the previous occurrence
        last[ch] = right
        best = max(best, right - left + 1)
    return best

Dry run on "abcabcbb": windows grow to "abc" (3), then each repeat moves left one past the previous occurrence; best stays 3. The check last[ch] >= left is essential: for "abba", when the final 'a' arrives its old index 0 is already outside the window. Full walkthrough: LeetCode 3 explained. The hardest member of this family, Minimum Window Substring, has its own guide: LeetCode 76 explained.

Longest Repeating Character Replacement (424) is the elegant one: a window is valid if length - maxFreq <= k. You never need to decrease maxFreq when shrinking, because only a larger maxFreq can produce a longer answer.

Pattern 4: Palindrome Problems

Check a palindrome with two pointers

Valid Palindrome (125) ignores non-alphanumerics and case. Do it in place with two pointers rather than building a cleaned copy, which saves O(n) memory and is what interviewers usually ask for in the follow-up.

public boolean isPalindrome(String s) {
    int i = 0, j = s.length() - 1;
    while (i < j) {
        char a = s.charAt(i), b = s.charAt(j);
        if (!Character.isLetterOrDigit(a)) { i++; continue; }
        if (!Character.isLetterOrDigit(b)) { j--; continue; }
        if (Character.toLowerCase(a) != Character.toLowerCase(b)) return false;
        i++; j--;
    }
    return true;
}

Valid Palindrome II (680), "delete at most one character": on the first mismatch, try skipping either side once and check the remainder is a palindrome. O(n).

Longest Palindromic Substring: expand around center

Every palindrome has a center: a character (odd length) or a gap between two characters (even length). There are 2n - 1 centers; expanding from each costs up to O(n), so O(n²) time and O(1) space, simpler and more memory-friendly than the O(n²) DP table.

def longest_palindrome(s: str) -> str:
    if not s:
        return ""
    best_l, best_r = 0, 0

    def expand(l, r):
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1
            r += 1
        return l + 1, r - 1          # last valid bounds

    for i in range(len(s)):
        for l, r in (expand(i, i), expand(i, i + 1)):
            if r - l > best_r - best_l:
                best_l, best_r = l, r
    return s[best_l:best_r + 1]

public String longestPalindrome(String s) {
    if (s.isEmpty()) return "";
    int start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
        int len = Math.max(expand(s, i, i), expand(s, i, i + 1));
        if (len > end - start + 1) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    return s.substring(start, end + 1);
}
private int expand(String s, int l, int r) {
    while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { l--; r++; }
    return r - l - 1;                // length of palindrome found
}

Dry run on "babad": center 1 ('a') expands to "bab" (length 3); center 2 ('b') to "aba" (also 3); even centers give nothing. Either answer is accepted. Counting all palindromic substrings (647) uses the same expansion and adds one per successful step. Manacher's algorithm achieves O(n), but it is rarely expected in interviews; mention it as the optimal bound.

Pattern 5: Stack-Based String Parsing

Signal: nesting (brackets, encoded repeats), "remove adjacent pairs", or evaluating expressions. The most recent unmatched thing must be handled first: last in, first out.

Valid Parentheses (20): push openers, and on a closer require the top to be the matching opener; the stack must be empty at the end. Remove All Adjacent Duplicates (1047): use a StringBuilder as the stack, deleting the last char when it equals the incoming one.

Representative problem: Decode String (394). "3[a2[c]]" becomes "accaccacc".

def decode_string(s: str) -> str:
    stack = []                 # (string built before '[', repeat count)
    cur, num = [], 0
    for ch in s:
        if ch.isdigit():
            num = num * 10 + int(ch)          # multi-digit counts like 12[ab]
        elif ch == '[':
            stack.append(("".join(cur), num))
            cur, num = [], 0
        elif ch == ']':
            prev, k = stack.pop()
            cur = [prev + "".join(cur) * k]
        else:
            cur.append(ch)
    return "".join(cur)

Trace for 3[a2[c]]: push ("", 3); collect "a"; push ("a", 2); collect "c"; on the first ']' build "a" + "cc" = "acc"; on the second ']' build "" + "acc" × 3. Forgetting multi-digit numbers is the most common bug here. The stack and queue guide covers more.

Pattern 6: Substring Search With KMP and the Z Algorithm

The naive search for pattern p (length m) in text t (length n) tries every alignment: O(n·m) worst case, for example t = "aaaa...ab", p = "aaab". Linear-time algorithms avoid re-reading text characters by precomputing structure in the pattern.

KMP: the LPS (failure) array

lps[i] is the length of the longest proper prefix of p[0..i] that is also a suffix of it. On a mismatch after matching j characters, we already know the last lps[j-1] characters of the text match the pattern's prefix, so we resume from there instead of restarting.

For p = "ABABCABAB" the LPS array is:

At i = 8, "ABAB" is both a prefix and a suffix of "ABABCABAB", so lps = 4.

def build_lps(p: str):
    lps = [0] * len(p)
    length, i = 0, 1               # length of current matched prefix
    while i < len(p):
        if p[i] == p[length]:
            length += 1
            lps[i] = length
            i += 1
        elif length > 0:
            length = lps[length - 1]   # fall back; do not advance i
        else:
            lps[i] = 0
            i += 1
    return lps

def kmp_search(text: str, p: str):
    if not p:
        return [0]
    lps, res, j = build_lps(p), [], 0
    for i, ch in enumerate(text):
        while j > 0 and ch != p[j]:
            j = lps[j - 1]
        if ch == p[j]:
            j += 1
        if j == len(p):
            res.append(i - j + 1)
            j = lps[j - 1]             # continue for overlapping matches
    return res

static int[] buildLps(String p) {
    int[] lps = new int[p.length()];
    for (int i = 1, len = 0; i < p.length(); ) {
        if (p.charAt(i) == p.charAt(len)) lps[i++] = ++len;
        else if (len > 0) len = lps[len - 1];
        else lps[i++] = 0;
    }
    return lps;
}

static int strStr(String text, String p) {         // first occurrence, LeetCode 28
    if (p.isEmpty()) return 0;
    int[] lps = buildLps(p);
    for (int i = 0, j = 0; i < text.length(); i++) {
        while (j > 0 && text.charAt(i) != p.charAt(j)) j = lps[j - 1];
        if (text.charAt(i) == p.charAt(j)) j++;
        if (j == p.length()) return i - j + 1;
    }
    return -1;
}

Complexity: O(n + m) time, O(m) space. The text pointer never moves backwards, and every fallback is paid for by an earlier advance.

The Z algorithm

z[i] is the length of the longest substring starting at i that matches a prefix of the string. To search, compute Z on p + "$" + t (with a separator absent from both); every position where z[i] == m is a match. It is often easier to remember than KMP.

def z_function(s: str):
    n = len(s)
    z = [0] * n
    l = r = 0                      # [l, r) is the rightmost window matching a prefix
    for i in range(1, n):
        if i < r:
            z[i] = min(r - i, z[i - l])        # reuse previously computed info
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        if i + z[i] > r:
            l, r = i, i + z[i]
    return z

def z_search(text, p):
    s = p + "\x00" + text
    z = z_function(s)
    return [i - len(p) - 1 for i in range(len(p) + 1, len(s)) if z[i] >= len(p)]

Where these show up in interviews

• Repeated Substring Pattern (459): s is periodic iff n % (n - lps[n-1]) == 0 and lps[n-1] > 0. (Or the trick: s is in (s + s)[1:-1].)
• Shortest Palindrome (214): compute LPS of s + "#" + reverse(s); the final value is the longest palindromic prefix.
• Rabin-Karp (rolling hash) is the other linear-expected option; it generalises to multiple patterns and to "longest duplicate substring" with binary search. Mention collision handling (verify on hash match) if you use it.

Building and Parsing Strings Without Bugs

The StringBuilder pitfall

// O(n^2): each += copies the whole accumulated string
String out = "";
for (int i = 0; i < n; i++) out += i;

// O(n): amortised O(1) appends, one copy at the end
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) sb.append(i);
String result = sb.toString();

In Python, collect parts in a list and call "".join(parts). CPython sometimes optimises s += x in place, but that is an implementation detail you should not rely on in an interview. In C++, s += c is amortised O(1) but s = s + c copies every time.

String to Integer (atoi): overflow-safe parsing

This question (LeetCode 8) is about discipline: skip leading spaces, read an optional sign, consume digits, stop at the first non-digit, and clamp to the 32-bit range before overflowing.

public int myAtoi(String s) {
    int i = 0, n = s.length(), sign = 1, result = 0;
    while (i < n && s.charAt(i) == ' ') i++;
    if (i < n && (s.charAt(i) == '+' || s.charAt(i) == '-')) {
        sign = s.charAt(i) == '-' ? -1 : 1;
        i++;
    }
    while (i < n && Character.isDigit(s.charAt(i))) {
        int d = s.charAt(i) - '0';
        if (result > (Integer.MAX_VALUE - d) / 10)          // next step would overflow
            return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
        result = result * 10 + d;
        i++;
    }
    return sign * result;
}

The check works for the negative side too: -2147483648 clamps to Integer.MIN_VALUE, which is the correct value.

Reverse Words and String Compression

Reverse Words in a String (151): in Python, " ".join(reversed(s.split())); in Java, split("\\s+") after trim(). The follow-up for mutable character arrays is the O(1)-space trick: reverse the whole array, then reverse each word. String Compression (443) is a read/write two-pointer problem in place, where counts above 9 must be written digit by digit.

Where String Problems Meet DP, Tries and Hashing

Some string questions belong to other topics, and recognising that early saves time:

• Two strings, subsequence or edit operations (LCS, Edit Distance, Distinct Subsequences, Interleaving String): dynamic programming on a 2D table. See DP on strings and Edit Distance explained.
• Dictionary of words with prefix queries (autocomplete, Word Search II, Replace Words): a trie. See trie problems.
• Segmenting a string into dictionary words: DP over prefixes, as in Word Break.
• Generate all combinations (letter combinations of a phone number, generate parentheses, palindrome partitioning): backtracking.
• Custom ordering: Largest Number (179) sorts by the comparator a + b vs b + a, with a special case when the result starts with "0".

String Practice List by Pattern

String Interview Pitfalls and What Interviewers Probe

Questions to ask before coding

1. Character set: lowercase only, ASCII, or Unicode? Decides array vs map.
2. Case and whitespace: is "Listen" an anagram of "Silent"? Do spaces count?
3. Return value: the substring, its length, or its starting index? Any valid answer, or the first?
4. Constraints: length up to 10⁵ rules out O(n²) expansions in tight limits; up to 1000 makes them fine.

Language traps

• Java == on strings compares references. It may pass for literals (string pool) and fail for computed strings. Always use equals.
• Java split takes a regex. "a.b".split(".") returns an empty array because "." matches everything; use split("\\."). Same for "|". Trailing empty strings are also dropped by default.
• Character arithmetic: 'a' + 1 is the int 98 in Java; cast back with (char). In C++, pass unsigned char to isalpha-family functions to avoid undefined behaviour on negative char values.
• Substring is not free: calling substring inside a loop can turn O(n) into O(n²). Pass indices instead.
• Reversing Unicode by char breaks surrogate pairs in Java; mention it if the interviewer raises internationalisation.

How to present a string solution

State the pattern and the invariant: "I keep a window with no repeated characters; left jumps past the last occurrence of a repeated character." Give complexity in terms of both n and the alphabet size where relevant ("O(n) time, O(min(n, alphabet)) space"). Then dry run on an input that exercises the edge, such as "abba" for the window problem or "a" for the palindrome problem. Interviewers at product companies consistently reward this narration; see how to think out loud in coding interviews.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.