Log inSign up
easyleetcodeNot Started

Valid Palindrome

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on leetcode
Lesson

Problem Statement

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters 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
Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:

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

Example 3:

Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters. Since an empty string reads the same forward and backward, it is a palindrome.

Constraints:

  • 1 <= s.length <= 2 * 105
  • s consists only of printable ASCII characters.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Filter characters on the fly using two converging pointers.
  • Handle case-insensitive ASCII comparison.
  • Safely guard inner skip loops against index out-of-bounds.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Checking palindrome properties ignoring whitespace, punctuation, and case.
  • Symmetric boundary comparisons with character skip conditions.

Algorithmic Decision Tree:

  • Checking palindrome properties ignoring whitespace, punctuation, and case.
  • Symmetric boundary comparisons with character skip conditions.

Connected Patterns:

Valid Palindrome IIReverse StringValid Anagram

1. Filter String and Reverse Compare

Intuition

Iterate through s. If a character is alphanumeric, convert to lowercase and append to string filtered. Check if filtered == reverse(filtered).

When to apply: Basic baseline comparison.

Algorithm

  1. Create string filtered = "".
  2. For c in s:
  3. If isAlphanumeric(c): filtered += toLowerCase(c).
  4. Return filtered == reverse(filtered).

Filtered Lowercase Copy & Reverse Comparison Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [a, m, a, n, a, p, l, a, n, a, c, a, n, a, l, p, a, n, a, m, a]
Current operationSTEP 1 OF 6
Observation: Strip punctuation and spaces, converting letters to lowercase
Visual state
Values and pointers at this exact step
array
S
a
m
a
n
a
p
l
a
n
a
c
a
n
a
l
p
a
n
a
m
a
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Variables at this step
Filtered
amanaplanacanalpanama
Length
21
Check / comparison
Filter non-alphanumeric chars and lowercase: "amanaplanacanalpanama".
Decision / next transition
Generate cleaned string of length 21 containing only alphanumeric characters.
Why this step matters

Observation: Strip punctuation and spaces, converting letters to lowercase.

Decision: Filtered string is "amanaplanacanalpanama" (length 21).

Invariant: Removes irrelevant punctuation.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <cctype>
4#include <algorithm>
5
6class Solution {
7public:
8 bool isPalindrome(std::string s) {
9 std::string filtered = "";
10 for (char c : s) {
11 if (isalnum(c)) {
12 filtered += tolower(c);
13 }
14 }
15 std::string rev = filtered;
16 std::reverse(rev.begin(), rev.end());
17 return filtered == rev;
18 }
19};
20
21int main() {
22 Solution sol;
23 std::cout << (sol.isPalindrome("A man, a plan, a canal: Panama") ? "true" : "false") << std::endl; // true
24 std::cout << (sol.isPalindrome("race a car") ? "true" : "false") << std::endl; // false
25 return 0;
26}

Time & Space Complexity

  • Time complexity: O(N) — Builds a filtered string of length up to N and reverses it.
  • Space complexity: O(N) auxiliary space

Why Brute Force Doesn't Scale:

Two pointers converge in a single pass with immediate early exit on the first mismatch.

Zero extra memory allocations; strict O(1) space.

2. Recursive Two Pointers Helper

Intuition

Define helper(left, right). Base case: left >= right return true. Skip invalid characters with helper. If toLower(s[left]) != toLower(s[right]), return false. Recurse on helper(left + 1, right - 1).

When to apply: Recursive functional formulation.

Algorithm

  1. Helper check(s, left, right):
  2. While left < right && !isalnum(s[left]): left++.
  3. While left < right && !isalnum(s[right]): right--.
  4. If left >= right: return true.
  5. If tolower(s[left]) != tolower(s[right]): return false.
  6. Return check(s, left + 1, right - 1).

Recursive Two Pointers Inward Scan Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [r, a, c, e, c, a, r]
Current operationSTEP 1 OF 6
Observation: Frame 1: isPal(0, 6)
Visual state
Values and pointers at this exact step
array
S
r
a
c
e
c
a
r
0
↑ l=0
1
2
3
4
5
6
↑ r=6
Variables at this step
Frame
isPal(0, 6)
Stack Depth
1
Match
true
Check / comparison
Call isPal(l=0, r=6). s[0] ('r') == s[6] ('r'). Match.
Decision / next transition
Outermost pair matches. Recurse inward on isPal(l=1, r=5).
Why this step matters

Observation: Frame 1: isPal(0, 6). s[0] == s[6] == 'r'.

Decision: Match confirmed. Recurse inward on isPal(1, 5).

Invariant: Outer boundary verified.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <cctype>
4
5class Solution {
6 bool check(const std::string& s, int l, int r) {
7 while (l < r && !isalnum(s[l])) l++;
8 while (l < r && !isalnum(s[r])) r--;
9 if (l >= r) return true;
10 if (tolower(s[l]) != tolower(s[r])) return false;
11 return check(s, l + 1, r - 1);
12 }
13public:
14 bool isPalindrome(std::string s) {
15 return check(s, 0, (int)s.size() - 1);
16 }
17};
18
19int main() {
20 Solution sol;
21 std::cout << (sol.isPalindrome("A man, a plan, a canal: Panama") ? "true" : "false") << std::endl; // true
22 return 0;
23}

Time & Space Complexity

  • Time complexity: O(N) — Recursion depth is up to N / 2.
  • Space complexity: O(N) recursion stack

3. Two Pointers Converging In-Place (Optimal)

Intuition

Initialize left = 0, right = s.length - 1. While left < right: 1. Advance left while left < right && !isalnum(s[left]). 2. Decrement right while left < right && !isalnum(s[right]). 3. Compare tolower(s[left]) != tolower(s[right]): if unequal, return false. 4. Advance left++ and decrement right--. Return true.

When to apply: The standard gold standard solution for minimal memory and early exit on mismatches.

Algorithm

  1. Initialize left = 0, right = s.length - 1.
  2. While left < right:
  3. While left < right && !isalnum(s[left]): left++.
  4. While left < right && !isalnum(s[right]): right--.
  5. If tolower(s[left]) != tolower(s[right]): return false.
  6. left++, right--.
  7. Return true.

Two-Pointer Inward Symmetry Convergence

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [r, a, c, e, c, a, r]
Current operationSTEP 1 OF 6
Observation: Initialize two pointers at extremities: left = 0 ('r') and right = 6 ('r')
Visual state
Values and pointers at this exact step
array
S
r
a
c
e
c
a
r
0
↑ L=0 ('r')
1
2
3
4
5
6
↑ R=6 ('r')
Variables at this step
L Pointer
0 ('r')
R Pointer
6 ('r')
Match
true
Check / comparison
s[0] ('r') == s[6] ('r'). Both are alphanumeric letters and match.
Decision / next transition
Match confirmed! Advance L to 1, R to 5.
Why this step matters

Observation: Initialize two pointers at extremities: left = 0 (r) and right = 6 (r).

Decision: Characters match: 'r' === 'r'. Advance left = 1 and decrement right = 5.

Invariant: Outer boundary is symmetric.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <cctype>
4
5class Solution {
6public:
7 bool isPalindrome(std::string s) {
8 int left = 0, right = (int)s.size() - 1;
9 while (left < right) {
10 while (left < right && !isalnum(s[left])) left++;
11 while (left < right && !isalnum(s[right])) right--;
12
13 if (tolower(s[left]) != tolower(s[right])) {
14 return false;
15 }
16 left++;
17 right--;
18 }
19 return true;
20 }
21};
22
23int main() {
24 Solution sol;
25 std::cout << (sol.isPalindrome("A man, a plan, a canal: Panama") ? "true" : "false") << std::endl; // true
26 std::cout << (sol.isPalindrome("race a car") ? "true" : "false") << std::endl; // false
27 std::cout << (sol.isPalindrome(" ") ? "true" : "false") << std::endl; // true
28 return 0;
29}

Time & Space Complexity

  • Time complexity: O(N) strictly — Each character is inspected at most twice (once by left or right pointer) with zero memory allocations.
  • Space complexity: O(1) extra space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Filter and Reverse StringO(N)O(N)Simple 2-line code in Python/JS.Allocates new filtered string and reversed copy.
2.Two Pointers In-Place (Optimal)OptimalO(N)O(1) extra spaceZero memory allocations, early exit on first mismatch, cache-friendly.Requires inner while loop boundary guards (left < right).

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Not including left < right inside the inner character skip while loops, causing pointer inversion and index out-of-bounds.

Pitfall 2:

Forgetting that numbers (0-9) are alphanumeric and must match identically.

Crucial Edge Cases to Validate:

  • String with only punctuation or whitespace (s = ' .,:; '): left and right pointers meet without comparing any characters, returning true.
  • Single alphanumeric character (s = a): left=0, right=0; loop terminates, returns true.
  • Strings with mixed case digits (s = 0P): Compares 0 and p, mismatch triggers false immediately.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Highlight the in-place two-pointer approach as superior to creating a sanitized string buffer.
  2. Show explicit ASCII range checks or isalnum / isLetterOrDigit.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why must the inner character skip loops contain the condition left < right?

Back to DSA Sheet