LeetCode 125 – Valid Palindrome

Valid Palindrome is a two-pointer warm-up with one genuinely nasty trap hidden in it. The algorithm takes a minute; the character handling is where people lose the problem, and there is a specific two-character input that breaks the clever version.

The problem

A phrase is a palindrome if, after converting uppercase to lowercase and removing all non-alphanumeric characters, it reads the same forwards and backwards. Given a string, return whether it is a palindrome.

"A man, a plan, a canal: Panama"  -> true    "amanaplanacanalpanama"
"race a car"                      -> false   "raceacar"
" "                               -> true    empty after filtering
""                                -> true
"0P"                              -> false   <- the one that breaks clever solutions
"ab_a"                            -> true    underscore is not alphanumeric

Alphanumeric, not alphabetic — digits count. And an empty string is a palindrome, which is the convention to confirm rather than assume.

Two pointers, skipping as they go

The obvious approach is to build a cleaned string and compare it with its reverse. It is correct and costs O(n) extra space. Say it, then improve it: two pointers walking inward, each skipping over characters that do not count, needs no allocation at all.

"A man, a plan"
 ^           ^
 left        right

skip anything non-alphanumeric from each side,
compare the two survivors case-insensitively,
step both inward.

Two things make the skipping safe. Each skip loop needs left < right in its own condition, not just the outer loop's — a string of pure punctuation would otherwise walk a pointer off the end. And the pointers must move after a successful comparison, not before, or the middle character is skipped on odd-length inputs.

The "0P" trap

A popular shortcut for case-insensitive comparison is to treat two characters as equal when they differ by 32, since 'a' - 'A' == 32. It is wrong:

'0' = 48      'P' = 80      80 - 48 = 32

so a "differ by 32" test says '0' and 'P' match.
They do not. "0P" is NOT a palindrome.

The gap of 32 between a letter's cases is a fact about letters, and the moment digits are in scope it stops identifying case pairs. The same applies to bit tricks like c | 32 — safe for letters, meaningless for anything else.

Use the library: Character.toLowerCase and Character.isLetterOrDigit in Java, str.lower() and str.isalnum() in Python. Knowing why the shortcut fails is worth more than the shortcut ever was.

Java

class Solution {
    public boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;

        while (left < right) {
            // Each skip loop needs its own bound, or pure punctuation walks off the end.
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
                left++;
            }
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
                right--;
            }

            // toLowerCase, NOT a "differs by 32" test -- see "0P".
            if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                return false;
            }

            left++;
            right--;
        }

        return true;
    }
}

When the string filters down to nothing, both skip loops stop at left == right, the comparison is a character against itself, and the loop ends. So " " and "" return true with no special case.

Character.isLetterOrDigit is Unicode-aware, so it accepts letters outside ASCII. That is usually what you want, and it is worth naming as an assumption — if the interviewer specifies ASCII only, the check becomes explicit ranges.

Python

class Solution:
    def isPalindrome(self, s: str) -> bool:
        left, right = 0, len(s) - 1

        while left < right:
            while left < right and not s[left].isalnum():
                left += 1
            while left < right and not s[right].isalnum():
                right -= 1

            if s[left].lower() != s[right].lower():
                return False

            left += 1
            right -= 1

        return True

The one-liner cleaned = [c.lower() for c in s if c.isalnum()] followed by cleaned == cleaned[::-1] is correct and much shorter. It also builds two lists to answer a yes/no question, so it is O(n) space where the two-pointer version is O(1). Offer it, name the trade, then write the pointers.

str.isalnum() is true for characters like '²' and non-Latin digits, so it is broader than [a-z0-9]. Fine under this problem's constraints; worth stating rather than absorbing.

Complexity

Each character is examined at most once by one pointer, so the nested loops are still linear — the same amortised argument as the sliding window in Minimum Window Substring: neither pointer ever moves backwards.

The pattern

Two pointers converging with a skip condition generalises well. Valid Palindrome II (680) allows deleting one character — on a mismatch, try skipping the left or the right and check whether either remainder is a palindrome, which is O(n) and not the O(n²) it looks like. Reverse Only Letters (917) uses the same skipping to swap in place. Symmetric Tree (101) is this idea on a tree.

What the interviewer is checking

• Alphanumeric, not alphabetic — digits are included.
• The "0P" case, or at least that you do not use a 32-gap trick.
• left < right inside each skip loop, not just the outer one.
• Empty string and whitespace-only string returning true.
• That you offer the clean-and-reverse version and then improve its space.
• Odd-length inputs, where the middle character compares with itself.
• That the nested loops are still O(n), with the reason.