Valid Palindrome: Two Pointer String Check

LeetCode 125, Valid Palindrome, is one of the first problems where two pointers click. The problem itself is simple. A string is a palindrome if it reads the same forward and backward, ignoring non-alphanumeric characters and case. But the implementation has a few spots where people trip up: skipping characters, normalizing case, and getting the loop termination right.

Let's build it up from scratch.

The problem

Given a string s, return True if it is a palindrome after converting all uppercase letters to lowercase and removing all non-alphanumeric characters. Return False otherwise.

A few examples:

• "A man, a plan, a canal: Panama" becomes "amanaplanacanalpanama", which reads the same both ways. Return True.
• "race a car" becomes "raceacar", which does not. Return False.
• " " becomes "", an empty string. An empty string is a palindrome. Return True.

The twist compared to a plain palindrome check is that you need to skip over spaces, punctuation, and other non-alphanumeric characters. You also need to treat 'A' and 'a' as the same character.

Brute force: clean first, then check

The most straightforward approach is to build a new string with only the lowercase alphanumeric characters, then check if it equals its reverse.

def is_palindrome_brute(s):
    cleaned = ""
    for c in s:
        if c.isalnum():
            cleaned += c.lower()

    return cleaned == cleaned[::-1]

This works perfectly. It is easy to understand and hard to mess up. But it uses O(n) extra space for the cleaned string (and another O(n) for the reversed copy). For an interview, the follow-up question is almost always: can you do it in-place?

Two pointers: O(1) space

The idea is simple. Place one pointer at the start of the string and one at the end. Move them toward each other, skipping any character that is not alphanumeric. At each step, compare the lowercase versions of the characters at both pointers. If they ever disagree, the string is not a palindrome. If the pointers meet or cross without a mismatch, it is.

def is_palindrome(s):
    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

That is the whole thing. Two pointers, two inner skip loops, one comparison, and you are done.

Visual walkthrough

Let's trace the algorithm on "race,car". The alphanumeric characters spell out "racecar", which is a palindrome. L (orange) is the left pointer, R (green) is the right pointer.

Notice what happens at step 4: R lands on the comma, which is not alphanumeric, so we skip it by moving R left. The skip loops handle this automatically. You never compare a non-alphanumeric character against anything.

Why two inner while loops?

This is the part that confuses people when they first see this solution. The outer while left < right loop runs once per comparison. But the inner skip loops can advance a pointer multiple positions in a row. Consider a string like "!!!a!!!". The left pointer starts at index 0, and the skip loop advances it all the way to index 3 before making a single comparison.

The key insight: each character in the string is visited at most once by each pointer. The left pointer only moves right. The right pointer only moves left. Even though there are nested loops, the total work across all iterations is O(n), not O(n^2).

Edge cases worth knowing

Empty or all-punctuation strings. After stripping non-alphanumeric characters, you get an empty string. An empty string is a palindrome by definition. The two pointer solution handles this naturally because left starts at 0, right starts at -1 (or the pointers cross during skipping), and the while loop never executes.

Single character. "a" is a palindrome. The pointers start at the same index, left < right is false, and we return True immediately.

Mixed case. "Aa" should return True. The .lower() call on both sides handles this. If you forget to normalize case, you will fail this test case.

Digits count as alphanumeric. "0P" should return False because '0' != 'p'. The isalnum() method correctly includes digits.

Complexity analysis

Time: O(n). Each pointer moves at most n positions total. The left pointer scans left to right, the right pointer scans right to left, and they meet in the middle. Every character is examined at most twice (once by each pointer in the worst case).

Space: O(1). Two integer pointers. No auxiliary data structures. This is the improvement over the brute force approach.

Both are O(n) time, but the two pointer solution avoids allocating a new string.

The building blocks

Valid Palindrome is built from one fundamental brick that shows up everywhere in two pointer problems.

Opposite-end convergence

Two pointers start at the extremes of the array (or string) and move inward based on a comparison. In this problem, the comparison is character equality. In other problems, it might be a sum comparison (Two Sum II) or a height comparison (Container With Most Water).

The shape is always the same:

1. Initialize left = 0, right = len - 1.
2. While left < right, compare the values at both pointers.
3. Based on the comparison, decide which pointer(s) to move.
4. The search space shrinks by at least one element per step.

Valid Palindrome adds a wrinkle: the skip step. Before comparing, you advance each pointer past non-alphanumeric characters. This is a minor extension to the core pattern, but it is worth drilling on its own because the same "skip invalid elements" idea appears in problems like Remove Duplicates from Sorted Array and Move Zeroes.

Other problems that use opposite-end convergence:

• Two Sum II (move based on sum vs. target)
• Container With Most Water (move the shorter side)
• Trapping Rain Water (process the side with the smaller running max)
• 3Sum (inner loop uses converging pointers on sorted subarray)

Common mistakes

Forgetting the left < right guard in skip loops. This causes index-out-of-bounds errors or incorrect results on strings with no alphanumeric characters.

Comparing before skipping. If you compare first and skip after, you might compare a space against a letter and incorrectly return False.

Using isalpha() instead of isalnum(). This misses digits. The problem says alphanumeric, which includes both letters and digits.

Not lowering both sides. If you only call .lower() on one side, mixed-case palindromes like "Aba" will fail.

Reading about it is not enough

Valid Palindrome is an "easy" problem. Most people can read the solution and nod along. But try writing it from scratch in two weeks without looking at any reference. The skip loop guards, the case normalization, the order of operations (skip then compare, not compare then skip). These small details are exactly what slip away.

The opposite-end convergence building block is tiny. It takes a few minutes to drill. But once it is in your long-term memory, assembling the full solution for any converging two pointer problem becomes mechanical. You are not memorizing Valid Palindrome. You are internalizing the technique that also solves Container With Most Water, Two Sum II, and the inner loop of 3Sum.

Related posts

• The Two Pointers Pattern - The foundational pattern behind the optimal solution
• Container With Most Water - A harder two pointer problem that also uses opposite-end convergence
• 3Sum - Uses converging two pointers as the inner loop after sorting