Is "racecar" a palindrome? You can answer that without thinking. Reverse the string mentally, compare. Done.

Now try "A man, a plan, a canal: Panama". Suddenly you're dealing with spaces, commas, colons, mixed casing. The question is the same — does this read the same forwards and backwards? — but the mechanics of answering it just got harder. You need to decide what counts as a “character” and what to ignore.

And then the problem gets genuinely interesting: what if a string almost works, and you're allowed to remove one character to fix it? Now you're not just checking — you're searching. A mismatch doesn't mean “no.” It means “maybe, if I make the right choice.” That branching decision is something you've never seen in array problems, and it's where the real learning lives.

This lesson walks through three escalating challenges: the basic palindrome check, the dirty-input version with inline filtering, and the one-removal variant that introduces a branching decision tree. Each one builds on the last.

Start with a string you're sure is a palindrome: "racecar". Place two pointers at opposite ends and step through it. At each pair, predict whether the characters match before advancing.

See what the pointers discover about the string's structure as they converge toward the center.

Notice the invariant: after checking k pairs, you know the first k and last k characters are mirror images. The unchecked region shrinks by two characters per step. When the pointers cross (or meet at the center), every pair has been verified.

This is an O(n) scan — each character is visited at most once. No auxiliary data structure, no string reversal, no extra memory. Just two indices and a comparison.

Real interview problems don't hand you a clean lowercase string. LeetCode 125 (Valid Palindrome) gives you "A man, a plan, a canal: Panama" — 30 characters including spaces, commas, a colon, and mixed case.

The core idea doesn't change: two pointers squeeze inward comparing characters. But now each pointer has an extra responsibility: skip anything that isn't a letter or digit. When the left pointer lands on a space or comma, advance it. When the right pointer lands on a colon, retreat it. Only compare when both pointers are on alphanumeric characters.

And comparisons must be case-insensitive. 'A' and 'a' are the same character for palindrome purposes.

Walk through the dirty string below. The first few steps are gated — predict whether to skip or compare at each position.

The key insight: filtering happens inline, interleaved with the convergence. You don't need to create a cleaned copy of the string first. Each pointer independently skips non-alphanumeric characters, and comparisons only happen between “real” characters.

This inline approach has a practical benefit beyond avoiding extra memory: it preserves the original indices. You always know exactly where each pointer is in the original string. That matters more than you might think — the next problem will show you why.

Two strategies for handling dirty input, and the right one depends on what comes next.

Before diving in, consider this: if you strip all the junk characters into a clean string first, then find a mismatch at index 5 in the cleaned string — what index is that in the original? Does it matter? (It will.)

Preprocessing strips all non-alphanumeric characters, lowercases everything, then runs the basic palindrome check on the cleaned string. Conceptually, it's two clean steps: clean(s) then isPalin(cleaned). Simple to reason about, easy to code. The cost is O(n) extra memory for the cleaned copy.

Inline filtering skips junk characters on the fly, like you just did. Each pointer independently advances past spaces, commas, colons -- only stopping on “real” characters. No extra string, O(1) extra space, and a single pass through the original.

For Valid Palindrome I, both work. Preprocessing is arguably cleaner code. But the choice stops being stylistic when the problem evolves.

When the problem demands indices

Consider the jump from Palindrome I to Palindrome II. In the one-removal variant, a mismatch at positions i and j means you need to check two sub-ranges: isPalin(s, i+1, j) and isPalin(s, i, j-1). Those i and j values are indices into the original string.

If you preprocessed, index 3 in the cleaned string is not index 3 in the original. The comma at position 4 was stripped, shifting everything. Now you need a reverse mapping from cleaned positions back to original positions -- which adds complexity and defeats the purpose of simplifying.

Inline filtering preserves original indices throughout. When you hit that mismatch, i and j point directly to the characters in question. No translation layer needed.

The general pattern for two-pointer string problems

This preprocessing-vs-inline tradeoff shows up in several problem families:

• Palindromes with dirty input (LC 125, 680): Inline wins when you need to report or branch on original positions. Preprocessing wins for one-shot clean checks.
• Anagram/frequency problems (LC 242, 438): Preprocessing (character frequency arrays) is almost always cleaner because position doesn't matter -- only character counts.
• Substring search (LC 76, 567): Inline filtering with a sliding window, because you need to know the window boundaries in the original string for the output.

The rule of thumb: if the answer involves positions in the original string, inline filtering is safer. If the answer only involves values or counts, preprocessing simplifies the logic.

Keep that in mind as we move to the harder variant.

New problem. LeetCode 680: Valid Palindrome II. You can remove at most one character to make the string a palindrome.

The string is "abca". Start the two-pointer convergence. The outer pair (a, a) matches. Move inward. Now you're comparing 'b' and 'c'. Mismatch.

In the basic version, you'd return false immediately. But the rules changed. You're allowed one removal. The question is: which character do you remove?

Two options:

• Remove the left mismatch character ('b' at index 1) and check if the remaining substring is a palindrome
• Remove the right mismatch character ('c' at index 2) and check if the remaining substring is a palindrome

Try both below.

In this example, you got lucky — both removals produce palindromes. "aca" and "aba" both work. But that's a special case. Most strings aren't this forgiving. When only one branch works, picking the wrong one first and giving up would produce the wrong answer.

This is the critical insight for Palindrome II: a mismatch spawns two sub-problems, and you must check both before concluding the string can't be fixed.

"abca" was generous — both removals worked. Now try strings where only one removal produces a palindrome. Pick the right one.

The takeaway is structural: when you hit a mismatch at positions i and j, you must check isPalindrome(s, i+1, j) and isPalindrome(s, i, j-1). If either returns true, the string is valid. If both return false, no single removal can save it.

It's tempting to use a heuristic — “remove whichever character appears less in the string” or “remove whichever one doesn't match its neighbor.” These heuristics are wrong. The only reliable approach is exhaustive: try both, check both.

This is a real bug pattern. Someone wrote Palindrome II code but only checks one removal branch — they try removing the left character, and if that doesn't work, they immediately return false without trying the right removal.

The input "cbbcc" exposes the bug. Trace through the execution below and watch the code produce the wrong answer. Then find the buggy line.

The fix is small but critical: instead of return isPalin after trying one side, try both sides. return isPalin(s, left+1, right) || isPalin(s, left, right-1). That || is the entire difference between a correct solution and a wrong one.

This is worth remembering because greedy single-branch checking feels right during an interview. “Just remove the left char and check” sounds reasonable until you encounter a string where only the right removal works. The exhaustive two-branch check is the only correct approach.

Back to Valid Palindrome I — the classic dirty-input version. Three blanks in the implementation: how to initialize the right pointer, how to test if a character is alphanumeric, and how to compare characters case-insensitively.

Put it all together. The string is "abcbda". Walk through the complete Palindrome II algorithm: converge, hit a mismatch, check both branches, determine the verdict.

This is the full decision tree for Palindrome II:

1. Converge pointers inward, comparing characters
2. If all pairs match: return true (already a palindrome)
3. If a mismatch at (i, j): check isPalin(s, i+1, j) and isPalin(s, i, j-1)
4. If either sub-check passes: return true
5. If both fail: return false

The time complexity is still O(n). The outer convergence is O(n), and each sub-check is at most O(n). You do at most one branching per string, so it's O(n) + O(n) = O(n) total.

Three strings. For each one: classify it. Is it already a palindrome, fixable with one removal, or broken beyond a single fix?

This is the synthesis — you need the basic check, the branching decision, and the exhaustive two-branch verification all working together in your head.

Tying it together: Valid Palindrome I and II use the same two-pointer convergence. The difference is what happens at a mismatch. In I, a mismatch means false. In II, a mismatch means “fork into two sub-problems and check both.” That fork is the entire algorithmic novelty of the harder variant — everything else is shared infrastructure.