Mastering LeetCode Problem 0125 | Mohammad.H Mohammadi

Problem 0125: Valid Palindrome

In the world of string problems on LeetCode, Valid Palindrome (Problem 125) is one of those questions that looks trivial at first glance but hides a couple of important interview patterns inside:

Two-pointer technique (from both ends),
Character filtering (only alphanumeric),
Case-insensitive comparison.

If you master this problem properly, it will pay off later in more advanced questions like:

680 – Valid Palindrome II (allowing at most one deletion),
Palindrome-based substring problems,
Complex parsing + validation tasks.

In this post, we’ll go through:

Problem overview
Why this is more than “just check if it’s a palindrome”
The two-pointer + filtering intuition
Step-by-step Python implementation
Detailed walkthrough on examples
Time & space complexity
Common mistakes in interviews
How this pattern generalizes to harder problems

1. Problem Overview

LeetCode 125 – Valid Palindrome

Given a string s, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Letters (a–z, A–Z) and digits (0–9) count.
Everything else (spaces, commas, colons, punctuation, etc.) should be ignored.
Uppercase and lowercase should be treated as the same.

1.1. Example 1

Input:  s = "A man, a plan, a canal: Panama"
Output: true
Explanation:
  After removing non-alphanumeric characters and lowercasing,
  we get "amanaplanacanalpanama", which is a palindrome.

1.2. Example 2

Input:  s = "race a car"
Output: false
Explanation:
  After filtering, "raceacar" is not a palindrome.

2. Why This Problem Is Subtle

At first, you might think:

“Easy, I’ll just reverse the string and compare.”

But there are three important constraints:

Only alphanumeric characters
- You must ignore spaces, commas, punctuation, etc.
Case-insensitive
- A and a are equal.
Efficiency & cleanliness
- Interviewers don’t want a messy solution with lots of ad-hoc filtering logic.
- They want to see either:
  - A clean filtered string + reverse check, or
  - A more optimal and elegant two-pointer solution.

This is what makes it a good filter question in interviews:
They want to see if you can apply a standard pattern (two-pointer) to slightly noisy input (non-alphanumeric characters, case differences).

3. Intuition: Two Pointers + Filtering

The core idea:

A palindrome reads the same forward and backward.
Instead of building a new filtered string and reversing it, we can check directly on the original string using two pointers:

3.1. High-level strategy

Convert the entire string to lowercase (to ignore case).
Use two indices:
- left starting at the beginning,
- right starting at the end.
While left < right:
- If s[left] is not alphanumeric, move left forward.
- If s[right] is not alphanumeric, move right backward.
- Once both point to alphanumeric characters, compare:
  - If s[left] != s[right] → not a palindrome.
  - If they’re equal → move both pointers inward and continue.
If the pointers cross without a mismatch → it is a palindrome.

This pattern is extremely powerful:

You don’t create extra strings (O(1) extra memory).
You traverse each character at most once (O(n) time).
Your code ends up clean and readable.

4. Python Implementation (LeetCode-Ready)

Here is a clean implementation, using exactly this two-pointer + filtering idea:

class Solution:
    def isPalindrome(self, s: str) -> bool:
        """
        Returns True if s is a valid palindrome, considering only alphanumeric
        characters and ignoring case. Otherwise returns False.
        """

        # Normalize to lowercase for case-insensitive comparison
        s = s.lower()
        left, right = 0, len(s) - 1

        while left < right:
            # Move left pointer to the next alphanumeric character
            while left < right and not s[left].isalnum():
                left += 1

            # Move right pointer to the previous alphanumeric character
            while left < right and not s[right].isalnum():
                right -= 1

            # Now both s[left] and s[right] are alphanumeric
            if s[left] != s[right]:
                return False

            # Move both pointers towards the center
            left += 1
            right -= 1

        # No mismatches found
        return True

4.1. Why this is clean and robust

s.lower() handles case-insensitivity in one line.
str.isalnum() handles the “only alphanumeric” condition cleanly.
We avoid building a new filtered string; we use the original string directly.
The logic is fully single-pass and in-place in terms of memory.

5. Step-by-Step Walkthrough

Let’s walk through the algorithm on a few representative inputs.

5.1. Example 1: `"A man, a plan, a canal: Panama"`

Lowercase:
```
"a man, a plan, a canal: panama"
```
Initial pointers:
- left = 0 → 'a'
- right = len(s) - 1 → 'a' (last character)

Iteration 1:

s[left] = 'a' (alnum), s[right] = 'a' (alnum)
Compare: 'a' == 'a' → OK
Move:
- left = 1
- right = right - 1

Iteration 2:

s[left] = ' ' (space, not alnum)
- Inner loop moves left forward until it hits 'm'.
s[right] might be 'm' or another letter depending on string length, but it will be alnum.

Compare:

'm' == 'm' → OK
Move pointers inward.

This continues:

Spaces, commas, and the colon are skipped.
Only letters/digits are compared.
Every pair matches.
Eventually left >= right and we never saw a mismatch → return True.

5.2. Example 2: `"race a car"`

Conceptual filtered + lowercased version is "raceacar".

Walking through:

r vs r → OK
a vs a → OK
c vs c → OK
e vs a → mismatch → return False.

The key: the mismatch detection happens as soon as character pairs disagree.

5.3. Example 3: `""` (empty string)

left = 0, right = -1.
while left < right is False immediately.
We never enter the loop → we return True.

By convention, an empty string is considered a palindrome.

5.4. Example 4: `".,,,!!!"`

All characters are non-alphanumeric.
left and right keep moving inward until left >= right.
No mismatches are found → returns True.

This is a subtle edge case:
With “no letters/digits at all”, we treat it as trivially symmetric.

6. Time and Space Complexity

Let n be the length of the string s.

6.1. Time Complexity: O(n)

Each pointer (left, right) moves at most n steps.
Inner loops skip non-alphanumeric characters, but each character is visited at most once by each pointer.
There are no nested loops over the entire string.

Formally:

$\text{Time Complexity} = O(n)$

6.2. Space Complexity: O(1)

We use only a handful of variables (left, right, modified s reference).
No auxiliary data structures like extra lists or arrays (beyond the input string).

$\text{Space Complexity} = O(1)$

(If you consider s.lower() creating a new string, that’s usually seen as O(n) transformation, but in interview context, focus is on extra data structures; here we don’t store more than a constant number of variables beyond that.)

7. Common Mistakes in Interviews

This problem appears simple, but candidates frequently stumble on subtle constraints. Here are typical pitfalls:

7.1. Mistake 1: Forgetting to Ignore Non-Alphanumeric Characters

Many candidates write something like:

s = s.lower()
return s == s[::-1]

This fails on:

"A man, a plan, a canal: Panama"

Because:

"aman, a plan, a canal: panama" != "amanap lanalac :lanap ,nam a"

They ignore spaces and punctuation requirements.

Fix: Either filter the string first or skip non-alnum characters in the loop.

7.2. Mistake 2: Not Handling Case-Insensitivity

Comparing directly without handling case:

if s[left] != s[right]:
    return False

Without lowercasing or uppercasing leads to incorrect behavior for inputs like "Aa" or "A man...".

Fix: Always normalize:

Either s = s.lower() at the start,
Or compare with s[left].lower() == s[right].lower().

7.3. Mistake 3: Building a Filtered String but Forgetting Digits

Some candidates only allow letters and forget digits:

filtered = [ch.lower() for ch in s if ch.isalpha()]

This breaks for inputs with digits like "0P" or "12321".

Correct: Use isalnum() instead of isalpha() to include digits.

7.4. Mistake 4: Overcomplicating the Solution

Sometimes people try to:

Use multiple extra strings,
Use regex-based heavy filtering,
Or write multiple passes over the string.

While such solutions may work, they often:

Increase code complexity,
Make the algorithm harder to explain under interview time pressure.

Interviewers prefer a clean, single-pass two-pointer solution.

7.5. Mistake 5: Off-by-One Errors with Pointers

Typical mistakes:

Using left <= right and mishandling the middle character,
Forgetting to check left < right in the inner loops before accessing s[left] or s[right].

Correct pattern:

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

Notice how left < right is present in the inner loops too, to avoid indexing issues.

8. From Valid Palindrome to Advanced Patterns

Once you’re comfortable with this pattern, you can naturally extend it to more complex problems.

8.1. LeetCode 680 – Valid Palindrome II

Problem: Check if a string can become a palindrome by deleting at most one character.
Core insight:
- Same two-pointer setup.
- On first mismatch, try:
  - Skipping left once.
  - Or skipping right once.
- Check if either resulting substring is a palindrome.

Your current solution for 125 essentially becomes a subroutine for 680.

8.2. Palindromic Substrings / Longest Palindromic Substring

There you usually use a different pattern:

Expand around center,
Or dynamic programming,
But the mental model of “mirror symmetry” from Valid Palindrome still helps.

8.3. General Data Cleaning + Validation Problems

The combination of:

Input normalization (lowercase, trimming),
Filtering irrelevant characters (isalnum()),
Two-pointer or linear scan,

appears in:

Log parsing,
Input sanitization,
Canonicalization tasks.

This is more than a LeetCode trick – it’s a real-life pattern.