String Coding Interview: Your Code Is Right Until the Input Gets Real

You've done the easy ones. Reverse a string. Check for anagram. Find the first non-repeating character. Every string interview warm-up, under five minutes, no sweat.

Then minimum window substring shows up. Or longest substring without repeating characters, now with Unicode input. Or a palindrome checker that passes 48 of 50 test cases and you have no idea why. Suddenly strings don't feel so friendly.

The failure modes aren't random. They cluster around the same six bugs, across every language, every problem type.

The Slice You Think Is Free

A common recursive palindrome checker:

def is_palindrome(s: str) -> bool:
    if len(s) <= 1:
        return True
    if s[0] != s[-1]:
        return False
    return is_palindrome(s[1:-1])

This reads well. Until you realize s[1:-1] is not O(1). String slicing in Python is O(k) where k is the length of the resulting substring, because Python creates a brand new string object by copying those characters. Every call. At the top level you copy n-2 characters, then n-4, then n-6. Total work: O(n²). Python is billing you hourly and you only found out after the job was done.

Pass indices instead:

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

No allocations. O(n) time, O(n) stack space.

The same trap shows up in sliding window code. If you're doing substring = s[left:right+1] inside a loop to track the current window, you're paying O(window_size) on every step. Use indices until you need to produce final output.

One more wrinkle: in Python, result += char inside a loop sometimes runs fast. CPython checks whether only one reference points to the string and tries to resize in place. This can make O(n²) code look like O(n) in quick benchmarks. It breaks the moment you keep a second reference anywhere. The optimization is an implementation detail, not a guarantee. Use a list and join at the end.

You're Reporting the Wrong Space Complexity

You write a function that counts character frequencies. Your interviewer asks "what's the space complexity?" You say O(n). Confidently. The correct answer is O(1).

The frequency table holds at most one entry per distinct character. For lowercase English letters, that's 26 entries regardless of input length. For ASCII, 128. Even for full Unicode, the character set is a fixed finite size. The table doesn't grow with the input, it grows with the alphabet.

def char_freq(s: str) -> dict:
    freq = {}
    for ch in s:
        freq[ch] = freq.get(ch, 0) + 1
    return freq
    # Space: O(1), bounded by alphabet size, not string length

This matters beyond interview scoring. When you know the space is O(1), you can keep multiple frequency tables without worrying about asymptotic cost. When you mistakenly believe it's O(n), you artificially limit your approach and give the interviewer a wrong answer with complete conviction, which is a fun combination.

The one exception: if the problem specifies an arbitrary alphabet (generic byte sequences, unbounded symbols), the frequency table genuinely is O(min(n, |Σ|)). Ask the clarifying question.

The Counter That Lies to You

This is the bug that sends you to 47 of 50. Three test cases standing between you and the green banner. You read through your code twice. Looks right. Feels right. Isn't.

The problem is minimum window substring (LeetCode 76). Find the smallest window in s containing all characters of t.

Here's the buggy version:

def min_window(s: str, t: str) -> str:
    need = set(t)          # BUG: tracks presence, not frequency
    window = {}
    formed = 0
    left = 0
    min_len = float('inf')
    result = ""

    for right, ch in enumerate(s):
        window[ch] = window.get(ch, 0) + 1
        if ch in need and window[ch] == 1:   # BUG: triggers on first occurrence
            formed += 1

        while formed == len(need):
            # shrink...

If t = "AABC", you need two copies of 'A'. This code marks the 'A' requirement satisfied the first time it sees any 'A'. It finds windows that don't actually satisfy the constraint.

Track frequency requirements, not just membership:

def min_window(s: str, t: str) -> str:
    need = {}
    for ch in t:
        need[ch] = need.get(ch, 0) + 1

    required = len(need)
    formed = 0
    window = {}
    left = 0
    min_len = float('inf')
    result = ""

    for right, ch in enumerate(s):
        window[ch] = window.get(ch, 0) + 1
        if ch in need and window[ch] == need[ch]:
            formed += 1

        while formed == required:
            if right - left + 1 < min_len:
                min_len = right - left + 1
                result = s[left:right+1]

            left_ch = s[left]
            window[left_ch] -= 1
            if left_ch in need and window[left_ch] < need[left_ch]:
                formed -= 1
            left += 1

    return result

formed increments only when window[ch] == need[ch], meaning you've accumulated exactly enough of that character. Five A's in the window when you need two? formed counted that requirement exactly once (when the second A arrived) and never double-counts.

The same bug surfaces in LeetCode 438 (Find All Anagrams) and any problem where the target contains duplicates.

Your Window Size Is Off by One

Quick check: left pointer at index 2, right pointer at index 7. How many characters are in this window?

If you said 5, go count on your fingers. The correct answer is 6. Window size is always right - left + 1.

This produces wrong answers, not crashes. The algorithm finds the right position but measures incorrectly, returning the wrong start index when you reconstruct the result. The tests that catch this involve small windows where the answer is visually obvious, and you'll spend ten minutes convinced your logic is correct.

# Wrong
if right - left > max_len:
    max_len = right - left
    best_left = left

# Correct
if right - left + 1 > max_len:
    max_len = right - left + 1
    best_left = left

Test this on a window you can count by hand before finalizing any sliding window implementation.

The Three Inputs Your Code Doesn't Handle

The empty string will find you. It always does.

Empty string. Many string algorithms crash or return garbage on "". Check if not s: return ... before your main logic, not inside the loop.

Single character. A palindrome checker that does s[0] != s[-1] when len(s) == 1 compares s[0] to itself, which always returns False. The loop body often assumes at least two characters exist. Check len(s) <= 1 first.

All identical characters. Sliding window problems with "at most k distinct characters" collapse to a full-string window when all characters match. Your shrink condition must not assume the window will actually shrink.

def verify_string_function(fn):
    assert fn("") is not None      # doesn't crash
    assert fn("a") is not None     # handles length 1
    assert fn("aaaa") is not None  # handles all-same

Run this check mentally before calling your implementation complete.

You Can't Modify That String In-Place

Python, Java, and JavaScript strings are immutable. This surprises people in two ways.

In Python, s[0] = 'x' raises a TypeError. You can't assign to string indices. When a problem says "modify in-place," convert to a mutable structure first:

# Python
chars = list(s)
chars[0] = 'x'
result = ''.join(chars)

# Java
char[] chars = s.toCharArray();
chars[0] = 'x';
String result = new String(chars);

In Java, == compares object references, not content. Two string literals with the same value may or may not be the same object due to string interning, so == sometimes returns true and sometimes doesn't. Always use .equals() in Java for string value comparison.

String a = new String("hello");
String b = new String("hello");

a == b       // false, different objects
a.equals(b)  // true, same content

It doesn't crash. It silently returns false when you expected true. Your code runs, produces wrong output, and gives you nothing to debug with. Worse.

Don't Assume ASCII

Most interview problems say "lowercase English letters," which bounds your alphabet to 26 characters. When a problem doesn't specify, or when you're writing production code, that assumption breaks.

The Turkish i problem is the canonical example. In Turkish locale, "I".toLowerCase() produces "ı" (dotless i), not "i". Code that does s.toLowerCase().equals(t.toLowerCase()) behaves differently depending on which locale the JVM is running in.

// Locale-dependent, wrong in Turkish locale
s.toLowerCase().equals(t.toLowerCase())

// Locale-independent
s.toLowerCase(Locale.ROOT).equals(t.toLowerCase(Locale.ROOT))

Your case-insensitive comparison works fine in every test, in every environment your team uses, and then fails exactly once in production because one server was configured with a Turkish locale. Somewhere, this has happened to someone. That person is now very religious about Locale.ROOT.

In interview settings, ask: "Can I assume ASCII, or lowercase English letters only?" The answer determines which tools you can safely reach for.

Six Checks Before Your String Coding Interview

Slicing is O(k), not O(1). Use index pairs in recursive functions and tight loops.
Character frequency tables are O(1) space. The alphabet is bounded, not the input.
Track frequency, not presence. Use window[ch] == need[ch] as your validity condition.
Window size is right - left + 1. Off by one here produces wrong lengths, not crashes.
Test empty, single character, and all-same inputs before declaring your solution done.
Use .equals() in Java and convert to a mutable structure before any in-place modification.

If you want to catch these under pressure, SpaceComplexity runs voice-based mock interviews where you have to explain complexity and edge cases out loud, not just get the code to pass.