valid-pallindrome

Valid Palindrome

May 31, 2026 — Prerna Sharma

Valid Palindrome – LeetCode #125 | DSA for Beginners

Two pointers from both ends — the classic mirror technique

Easy Two Pointers String

Problem Statement

Given

A string s. Return true if it is a palindrome, considering only alphanumeric characters and ignoring case.

Examples

Input: "A man, a plan, a canal: Panama" → true
Input: "race a car" → false
Input: " " → true (empty after filtering)

What is a Palindrome? 🔤

A palindrome reads the same forwards and backwards. "racecar", "madam", "level" are all palindromes. The tricky part here: we must ignore spaces, punctuation, and case.

After cleaning: "amanaplanacanalpanama"

…

L → ← R

Left and right pointers march toward each other, comparing characters

Approaches at a Glance

🐌 Brute Force (Clean & Reverse)

Filter to alphanumeric, lowercase, compare with its reverse

Time: O(n) Space: O(n)

⚡ Two Pointers (Optimal)

Two indices shrinking inward, skip non-alphanumeric in place

Time: O(n) Space: O(1)

Approach 1 — Brute Force (Clean & Reverse)

Strip all non-alphanumeric characters, lowercase everything, then check if the resulting string equals its reverse.

🔍 Dry Run — Brute Force

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

Step	Result
1. toLowerCase()	"a man, a plan, a canal: panama"
2. remove non-alphanumeric	"amanaplanacanalpanama"
3. reversed	"amanaplanacanalpanama"
4. cleaned === reversed?	✅ true

Approach 2 — Two Pointers (Optimal) ⚡

No extra string needed. Start with left = 0 and right = s.length - 1. Skip non-alphanumeric characters from either end. Compare the characters. If they differ → false. Keep moving inward until the pointers cross.

Start: left = 0, right = s.length - 1
Skip non-alphanumeric from the left with inner while loop
Skip non-alphanumeric from the right with inner while loop
Compare s[left].toLowerCase() vs s[right].toLowerCase()
If mismatch → return false. Else left++, right--
Pointers cross → return true

⚠️ Key detail: The custom isAlphanumeric(char) uses charCodeAt() directly — no regex, no built-in method. It checks ASCII ranges: A–Z (65–90), a–z (97–122), 0–9 (48–57). Faster and shows deeper understanding in interviews.

🔍 Dry Run — Two Pointers

Input: "race a car" → expect false

Step	L	R	s[L]	s[R]	Match?
1	0	9	r	r	✅
2	1	8 (skip space)	a	a	✅
3	2	6 (skip space)	c	c	✅
4	3	4 (skip space)	e	a	❌ return false

Input: "A man, a plan, a canal: Panama" → expect true

Step	L char	R char	Match?
1 (skip ,: spaces)	a	a	✅
2	m	m	✅
3	a	a	✅
4	n	n	✅
… (all match)	…	…	✅
Final	L >= R — pointers crossed		✅ return true

Time & Space Complexity

Approach	Time	Space	Note
Brute Force (Reverse)	O(n)	O(n)	Creates a new cleaned + reversed string
Two Pointers	O(n)	O(1)	No extra space — only two index variables

Key Insight: Both are O(n) time, but Two Pointers wins on space — O(n) vs O(1). No extra string created. The custom isAlphanumeric with char codes is also faster than regex.

Code — All Approaches × All Languages

Approach 1 🐌 Brute Force — Clean & Reverse O(n) O(n) space

JavaScript Python Java C++

Approach 2 ⚡ Two Pointers — Custom isAlphanumeric (Optimal) O(n) O(1) space

💡 isAlphanumeric checks ASCII codes directly — no regex, no built-in overhead.
A–Z = 65–90 | a–z = 97–122 | 0–9 = 48–57

JavaScript Python Java C++

🎯 Interview Tip: Two Pointers is the go-to for palindrome checks. Always handle "skip invalid characters" — interviewers love testing this edge case! Using a custom isAlphanumeric with char codes shows you understand what's happening under the hood.