LeetCode 125 — Valid Palindrome | Full Solution Explained

Difficulty	Pattern	Asked At	LeetCode Link
Easy	Two Pointers (Opposite Ends)	Facebook, Microsoft, Apple, Uber	leetcode.com/problems/valid-palindrome

📌  This is part of the Two Pointers series on Daily Dev Notes. LeetCode 125 is the perfect first Two Pointers problem to solve — it’s easy, clean, and teaches you the exact same pattern used in harder problems like 3Sum and Trapping Rain Water.

Valid Palindrome is one of those problems that looks almost too simple at first.

‘Just reverse the string and compare’ — that’s what most beginners think. And that does work. But there’s a much cleaner O(1) space solution using Two Pointers that avoids creating any new strings at all.

More importantly, this problem has a twist: you need to ignore non-alphanumeric characters (spaces, punctuation) and treat uppercase and lowercase as the same. That’s where most people make mistakes.

We’ll go through three approaches in this post — from simple to optimal — so you understand the full picture.

The Problem Statement

A phrase is a palindrome if, after converting all uppercase letters to lowercase and removing all non-alphanumeric characters, it reads the same forward and backward.

Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

Example 1:
  Input:  s = "A man, a plan, a canal: Panama"
  Output: true
  Why:    After cleaning → "amanaplanacanalpanama"
          This reads the same forwards and backwards.
 
Example 2:
  Input:  s = "race a car"
  Output: false
  Why:    After cleaning → "raceacar"
          "raceacar" reversed is "racaecar" — NOT the same.
 
Example 3:
  Input:  s = " "
  Output: true
  Why:    After cleaning → "" (empty string)
          An empty string is a palindrome by definition.

Breaking Down the Requirements

Requirement	What it means in code
Ignore non-alphanumeric characters	Skip spaces, commas, colons, exclamation marks, etc.
Case-insensitive comparison	Treat ‘A’ and ‘a’ as equal — convert to lowercase before comparing
Check palindrome	Characters must read the same from left and from right
Empty string after cleaning	Return true — empty string is considered a valid palindrome

💡  The most common bug in this problem is forgetting to skip non-alphanumeric characters when moving the pointers. Both pointers must skip over invalid characters before comparing.

Approach 1 — Clean the String First (Simple, But O(n) Space)

The most straightforward approach: first clean the string by keeping only alphanumeric characters converted to lowercase, then check if the cleaned string equals its reverse.

This is easy to write and understand — great as a starting point in an interview before optimising.

C++ Solution

#include <string>
#include <algorithm>
using namespace std;
 
class Solution {
public:
    bool isPalindrome(string s) {
        // Step 1: clean the string
        string cleaned = "";
        for (char c : s) {
            if (isalnum(c)) {
                cleaned += tolower(c);  // keep only alphanumeric, lowercase
            }
        }
 
        // Step 2: check if cleaned string == its reverse
        string reversed = cleaned;
        reverse(reversed.begin(), reversed.end());
 
        return cleaned == reversed;
    }
};

Python Solution

class Solution:
    def isPalindrome(self, s: str) -> bool:
        # Step 1: clean the string
        cleaned = ""
        for c in s:
            if c.isalnum():
                cleaned += c.lower()  # keep only alphanumeric, lowercase
 
        # Step 2: check if cleaned string == its reverse
        return cleaned == cleaned[::-1]

JavaScript Solution

var isPalindrome = function(s) {
    // Step 1: clean the string using regex
    const cleaned = s.toLowerCase().replace(/[^a-z0-9]/g, "");
 
    // Step 2: check if cleaned string == its reverse
    const reversed = cleaned.split("").reverse().join("");
 
    return cleaned === reversed;
};

Metric	Approach 1 (Clean + Reverse)	Notes
Time Complexity	O(n)	One pass to clean, one pass to reverse, one pass to compare
Space Complexity	O(n)	Creates a new cleaned string of length up to n
LeetCode Result	Accepted	Works fine — but uses extra space

⚠️  This approach is accepted on LeetCode, but uses O(n) extra space. If an interviewer asks ‘can you do it in O(1) space?’, this is where you move to the Two Pointers solution.

Approach 2 — Two Pointers (Optimal — O(1) Space)

Instead of creating a cleaned string, we use two pointers on the original string and skip non-alphanumeric characters as we go.

This is the optimal solution. No extra string. No reverse. Just two pointers moving inward.

The Algorithm

• Start left pointer at index 0 (beginning of string)
• Start right pointer at index s.length – 1 (end of string)
• While left < right:
•     Skip left pointer forward if s[left] is NOT alphanumeric
•     Skip right pointer backward if s[right] is NOT alphanumeric
•     If both are now alphanumeric, compare them (case-insensitive)
•     If they don’t match → return false
•     If they match → move both pointers inward
• If we finish the loop without finding a mismatch → return true

🔑  The only difference from a basic palindrome check is the extra step: skip non-alphanumeric characters before comparing. Everything else is identical to the Two Pointers palindrome template.

Step 3 — Full Dry Run

Let’s trace through Example 1 character by character.

Dry Run

Input: "A man, a plan, a canal: Panama"
Index:  0123456789...
 
After we trace the pointers on the ORIGINAL string (not cleaned):
- Non-alphanumeric characters (spaces, commas, colons) get SKIPPED
- All comparisons are case-insensitive

Step	left char	right char	Action	Match?
1	A (idx 0)	a (idx 29)	Both alphanumeric — compare ‘a’ vs ‘a’	YES — move both inward
2	m (idx 2)	m (idx 27)	Both alphanumeric — compare ‘m’ vs ‘m’	YES — move both inward
3	a (idx 3)	a (idx 25)	Both alphanumeric — compare ‘a’ vs ‘a’	YES — move both inward
4	n (idx 4)	n (idx 23)	Both alphanumeric — compare ‘n’ vs ‘n’	YES — move both inward
5	a (idx 6)	a (idx 21)	left skips comma+space, compare ‘a’ vs ‘a’	YES — move both inward
6	p (idx 8)	P (idx 20)	Both alphanumeric — compare ‘p’ vs ‘p’	YES — move both inward
7	l (idx 9)	a (idx 18)	Both alphanumeric — compare ‘l’ vs ‘a’	YES — move both inward
…	…	…	Continuing…	All match
End	left >= right	—	Loop ends	Return TRUE

✅  All characters match after skipping non-alphanumeric ones. Result: true — it IS a valid palindrome.

Now let’s trace Example 2 to see a FALSE case.

Dry Run

Input: "race a car"
Cleaned mentally: "raceacar"

Step	left char	right char	Action	Match?
1	r (idx 0)	r (idx 9)	Compare ‘r’ vs ‘r’	YES — move both
2	a (idx 1)	a (idx 8)	Compare ‘a’ vs ‘a’	YES — move both
3	c (idx 2)	c (idx 7)	Compare ‘c’ vs ‘c’	YES — move both
4	e (idx 3)	a (idx 6)	Compare ‘e’ vs ‘a’	NO — MISMATCH → return false

✅  Mismatch at step 4: ‘e’ != ‘a’. Result: false — it is NOT a valid palindrome.

Step 4 — Optimal Two Pointers Solution

C++ Solution

#include <string>
#include <cctype>
using namespace std;
 
class Solution {
public:
    bool isPalindrome(string s) {
        int left  = 0;
        int right = s.length() - 1;
 
        while (left < right) {
 
            // skip non-alphanumeric from the left
            while (left < right && !isalnum(s[left])) {
                left++;
            }
 
            // skip non-alphanumeric from the right
            while (left < right && !isalnum(s[right])) {
                right--;
            }
 
            // compare current characters (case-insensitive)
            if (tolower(s[left]) != tolower(s[right])) {
                return false;  // mismatch found — not a palindrome
            }
 
            // characters matched — move both pointers inward
            left++;
            right--;
        }
 
        return true;  // all characters matched
    }
};

Python Solution

class Solution:
    def isPalindrome(self, s: str) -> bool:
        left  = 0
        right = len(s) - 1
 
        while left < right:
 
            # skip non-alphanumeric from the left
            while left < right and not s[left].isalnum():
                left += 1
 
            # skip non-alphanumeric from the right
            while left < right and not s[right].isalnum():
                right -= 1
 
            # compare current characters (case-insensitive)
            if s[left].lower() != s[right].lower():
                return False  # mismatch found — not a palindrome
 
            # characters matched — move both pointers inward
            left  += 1
            right -= 1
 
        return True  # all characters matched

JavaScript Solution

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function(s) {
    let left  = 0;
    let right = s.length - 1;
 
    // helper: check if character is alphanumeric
    const isAlphanumeric = (c) => /[a-zA-Z0-9]/.test(c);
 
    while (left < right) {
 
        // skip non-alphanumeric from the left
        while (left < right && !isAlphanumeric(s[left])) {
            left++;
        }
 
        // skip non-alphanumeric from the right
        while (left < right && !isAlphanumeric(s[right])) {
            right--;
        }
 
        // compare current characters (case-insensitive)
        if (s[left].toLowerCase() !== s[right].toLowerCase()) {
            return false;  // mismatch found — not a palindrome
        }
 
        // characters matched — move both pointers inward
        left++;
        right--;
    }
    return true;  // all characters matched
};

Step 5 — Complexity Analysis

Metric	Approach 1 (Clean + Reverse)	Approach 2 (Two Pointers)	Why
Time	O(n)	O(n)	Both scan the string once — same time complexity
Space	O(n)	O(1)	Approach 1 creates a new string. Approach 2 uses only two integer pointers.

🚀  Both approaches are O(n) time but Two Pointers wins on space — O(1) vs O(n). For large strings, this is a meaningful difference. Interviewers always prefer the O(1) space solution.

Why Time is O(n) for Two Pointers

• left starts at 0 and only ever increases
• right starts at n-1 and only ever decreases
• The skipping inner loops are NOT O(n) each — across the entire run, left and right together move at most n steps total
• Each character is visited at most once by either pointer
• Total work: O(n)

💡  This is a common confusion — people see nested while loops and think O(n²). But since left and right together can only move n steps total across ALL iterations, it’s still O(n).

Step 6 — Tricky Cases That Catch Beginners

Tricky Case 1 — All Non-Alphanumeric Characters

Input:  " "  (just a space)
Process: left=0, right=0
         left skips the space → left becomes 1
         Now left >= right → loop ends
Output: true
 
Reason: After removing non-alphanumeric chars, string is empty.
        Empty string is a palindrome.

✅  Our solution handles this correctly. The inner while loops skip the space, left becomes 1, right stays 0, left >= right, loop exits, return true.

Tricky Case 2 — Single Character

Input:  "a"
Process: left=0, right=0
         left < right is FALSE immediately
         Loop never runs
Output: true
 
Reason: A single character always reads the same both ways.

Tricky Case 3 — Numbers in the String

Input:  "A1b2B1a"
Cleaned: "a1b2b1a"
Process: 'a'=='a', '1'=='1', 'b'=='b', middle is '2'
Output: true
 
Reason: Numbers ARE alphanumeric and must be compared normally.
        Do not accidentally skip digits.

⚠️  A common mistake is only checking for letters and forgetting to include digits as valid characters. Always use isalnum() — not isalpha() — which includes both letters AND digits.

Tricky Case 4 — Mixed Case With Symbols

Input:  "0P"
Cleaned: "0p"
Process: '0' vs 'p' → '0' != 'p'
Output: false
 
Reason: '0' (digit zero) and 'p' (letter) are different characters.
        Case-insensitive only affects letters, not digits.

Step 7 — Edge Cases Summary

Edge Case	Input	Output	Reason
Empty string	“”	true	Empty string is a palindrome
Single space	” “	true	After cleaning → empty → palindrome
Single character	“a”	true	One char always palindrome
Only numbers	“12321”	true	Numbers are alphanumeric, compared normally
Numbers that don’t match	“12345”	false	‘1’!=’5′ at first comparison
All same character	“aaaa”	true	All chars match
Mixed case	“AbBa”	true	‘a’==’a’, ‘b’==’b’ case-insensitively
Symbols only	“.,!”	true	After cleaning → empty → palindrome

✅  Our Two Pointers solution handles every single one of these correctly without any special case code.

Step 8 — How to Explain This in an Interview

Valid Palindrome is an Easy problem but interviewers at FAANG companies use it to test clarity of thought. Here’s the script:

• Step 1 — Clarify: ‘So we ignore spaces and punctuation, treat uppercase and lowercase as equal, and check if what’s left is a palindrome?’
• Step 2 — Simple approach: ‘I can clean the string, reverse it, and compare. That’s O(n) time and O(n) space.’
• Step 3 — Optimise: ‘Can I avoid creating the cleaned string? Yes — using Two Pointers on the original string, skipping non-alphanumeric characters as I go. That’s O(n) time and O(1) space.’
• Step 4 — Dry run: Trace ‘A man, a plan, a canal: Panama’ showing pointer movement and skipping.
• Step 5 — Code: Write the Two Pointers solution with the inner while loops for skipping.
• Step 6 — Complexity: ‘O(n) time — each character visited once. O(1) space — no extra string.’
• Step 7 — Edge cases: Mention empty string, single character, all non-alphanumeric.

💡  Mention BOTH approaches — simple first, then optimised. This shows you can code a working solution quickly AND think about optimisation. Interviewers appreciate that thought process.

Comparing All Three Approaches

Approach	Time	Space	When to Use
Built-in reverse (JS one-liner)	O(n)	O(n)	Quick scripting, not interviews
Clean string + reverse	O(n)	O(n)	First answer in interview — easy to explain
Two Pointers (optimal)	O(n)	O(1)	Final answer — always preferred in interviews

📌  In a real interview, mention the clean+reverse approach first (shows you can solve it), then say ‘but I can do better on space’ and write the Two Pointers solution. That’s the ideal interview flow.

Final Solution at a Glance

C++

bool isPalindrome(string s) {
    int left = 0, right = s.length() - 1;
 
    while (left < right) {
        while (left < right && !isalnum(s[left]))  left++;
        while (left < right && !isalnum(s[right])) right--;
 
        if (tolower(s[left]) != tolower(s[right])) return false;
 
        left++;
        right--;
    }
    return true;
}

Time Complexity	Space Complexity	LeetCode Result	Difficulty
O(n)	O(1)	Accepted ✓	Easy

Wrapping Up

Valid Palindrome is a deceptively simple problem. The logic is clean — two pointers moving inward, skipping non-alphanumeric characters, comparing case-insensitively. But the details matter.

The three things to always remember for this problem:

• Use isalnum() — not isalpha() — to include digits as valid characters
• Skip non-alphanumeric characters with INNER while loops — not if statements
• Always check left < right inside the inner while loops to avoid going out of bounds

Once these habits are locked in, you’ll solve this problem in under 5 minutes every time — and be ready to apply the same Two Pointers skeleton to much harder problems.

📬  This is part of the Two Pointers series on Daily Dev Notes. Next up: LeetCode 15 — 3Sum. It uses Two Pointers inside a for loop — a bit harder but very doable after this. Subscribe to the newsletter so you don’t miss it.

Got a question about any step? Drop it in the comments below — I reply to every one.