Valid Palindrome

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.

What to notice first

• “Alphanumeric” means letters (a-z, A-Z) and digits (0-9) — skip spaces, punctuation, etc.
• Always convert to the same case before comparing.
• Two pointers avoids creating a cleaned copy → O(1) extra space.

Examples

Input	Output	Reason
"A man, a plan, a canal: Panama"	true	Cleaned: "amanaplanacanalpanama" is a palindrome
"race a car"	false	Cleaned: "raceacar" is not a palindrome
" "	true	After cleaning: "" — empty string is a palindrome

Constraints

• 1 <= s.length <= 2 × 10^5
• s consists only of printable ASCII characters

Real-World Applications

Where this pattern appears

• Input sanitization — checking if a DNA sequence or serial number is palindromic after stripping delimiters
• Symmetric routing — checking if a path identifier is the same forward and backward
• Data integrity — palindromic checksums in some encoding schemes
• Natural language processing — detecting palindromes in text after normalization

Complexity Comparison

Approach	Time	Space	Best When
Two Pointers	O(n)	O(1)	Preferred — no extra allocation
Clean Then Check	O(n)	O(n)	Clarity, simpler code

Approach 1: Two Pointers (Recommended)

★ Recommended

Place left at the start and right at the end of the string. Skip non-alphanumeric characters on both sides, then compare the lowercased characters at each pointer. If any mismatch is found, return false. If the pointers meet or cross, return true.

⏱ Time O(n) Single pass 💾 Space O(1) No extra allocation

Step-by-step Example

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

Cleaned view (not actually built): "amanaplanacanalpanama"

Step	left char	right char	match?	action
1	'A' → a	'a'	✓	advance both
2	m	'm'	✓	advance both
3	a	'a'	✓	advance both
…	right pointer skips ':', ' '	left skips ',', ' '	…	skip non-alphanumeric
last	pointers meet	—	—	return true

Key behavior — skipping non-alphanumeric characters:

When the left pointer lands on ',' or ' ', the inner while loop advances it until it finds an alphanumeric character without doing any comparison. The same happens on the right side.

Animated walkthrough

Two pointers converging on 'A man, a plan, a canal: Panama'

Use Next or Autoplay to watch the left and right pointers skip punctuation and spaces, then compare alphanumeric characters.

Back Autoplay Next Reset

Step 1 of 4 Target: All characters matched

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function isPalindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        while left < right and not isAlphanumeric(s[left]):
            left++
        while left < right and not isAlphanumeric(s[right]):
            right--
        if lower(s[left]) != lower(s[right]):
            return false
        left++; right--
    return true

Solution Code

Python

valid_palindrome_two_pointer.py

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

C++

valid_palindrome_two_pointer.cpp

#include <string>
using namespace std;

class Solution {
public:
    bool isPalindrome(string s) {
        int left = 0, right = (int)s.size() - 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;
    }
};

Java

valid_palindrome_two_pointer.java

class Solution {
    public boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            while (left < right && !Character.isLetterOrDigit(s.charAt(left)))  left++;
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) right--;
            if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

JavaScript

valid_palindrome_two_pointer.js

function isPalindrome(s) {
    function isAlphanumeric(c) {
        return /[a-zA-Z0-9]/.test(c);
    }
    let left = 0, right = s.length - 1;
    while (left < right) {
        while (left < right && !isAlphanumeric(s[left]))  left++;
        while (left < right && !isAlphanumeric(s[right])) right--;
        if (s[left].toLowerCase() !== s[right].toLowerCase()) return false;
        left++;
        right--;
    }
    return true;
}

Rust

valid_palindrome_two_pointer.rs

impl Solution {
    pub fn is_palindrome(s: String) -> bool {
        let bytes: Vec<u8> = s.bytes().collect();
        let mut left = 0usize;
        let mut right = bytes.len().saturating_sub(1);
        while left < right {
            while left < right && !bytes[left].is_ascii_alphanumeric() {
                left += 1;
            }
            while left < right && !bytes[right].is_ascii_alphanumeric() {
                right -= 1;
            }
            if bytes[left].to_ascii_lowercase() != bytes[right].to_ascii_lowercase() {
                return false;
            }
            left += 1;
            if right == 0 { break; }
            right -= 1;
        }
        true
    }
}

Go

valid_palindrome_two_pointer.go

import "unicode"

func isPalindrome(s string) bool {
  runes := []rune(s)
  left, right := 0, len(runes)-1
  for left < right {
    for left < right && !unicode.IsLetter(runes[left]) && !unicode.IsDigit(runes[left]) {
      left++
    }
    for left < right && !unicode.IsLetter(runes[right]) && !unicode.IsDigit(runes[right]) {
      right--
    }
    if unicode.ToLower(runes[left]) != unicode.ToLower(runes[right]) {
      return false
    }
    left++
    right--
  }
  return true
}

Approach 2: Clean Then Check

✓ Simple

Filter the string to keep only alphanumeric characters, lowercase them all, then check if the resulting string equals its own reverse. Simple and readable, but allocates O(n) extra space.

⏱ Time O(n) Single pass 💾 Space O(n) Cleaned string storage

Pseudocode

function isPalindrome(s):
    cleaned = [c.lower() for c in s if c.isalnum()]
    return cleaned == reversed(cleaned)

Solution Code

Python

valid_palindrome_clean.py

def is_palindrome(s: str) -> bool:
    cleaned = [c.lower() for c in s if c.isalnum()]
    return cleaned == cleaned[::-1]

C++

valid_palindrome_clean.cpp

#include <algorithm>
#include <string>
using namespace std;

class Solution {
public:
    bool isPalindrome(string s) {
        string cleaned;
        for (char c : s) {
            if (isalnum(c)) cleaned += tolower(c);
        }
        string reversed = cleaned;
        reverse(reversed.begin(), reversed.end());
        return cleaned == reversed;
    }
};

Java

valid_palindrome_clean.java

class Solution {
    public boolean isPalindrome(String s) {
        StringBuilder cleaned = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (Character.isLetterOrDigit(c)) {
                cleaned.append(Character.toLowerCase(c));
            }
        }
        String forward = cleaned.toString();
        String backward = cleaned.reverse().toString();
        return forward.equals(backward);
    }
}

JavaScript

valid_palindrome_clean.js

function isPalindrome(s) {
    const cleaned = s.toLowerCase().replace(/[^a-z0-9]/g, '');
    return cleaned === cleaned.split('').reverse().join('');
}

Rust

valid_palindrome_clean.rs

impl Solution {
    pub fn is_palindrome(s: String) -> bool {
        let cleaned: Vec<char> = s
            .chars()
            .filter(|c| c.is_alphanumeric())
            .map(|c| c.to_ascii_lowercase())
            .collect();
        let reversed: Vec<char> = cleaned.iter().cloned().rev().collect();
        cleaned == reversed
    }
}

Go

valid_palindrome_clean.go

import "unicode"

func isPalindrome(s string) bool {
  var cleaned []rune
  for _, c := range s {
    if unicode.IsLetter(c) || unicode.IsDigit(c) {
      cleaned = append(cleaned, unicode.ToLower(c))
    }
  }
  n := len(cleaned)
  for i := 0; i < n/2; i++ {
    if cleaned[i] != cleaned[n-1-i] {
      return false
    }
  }
  return true
}

Common mistakes

Watch for these pitfalls

• Forgetting to handle digits — '0'–'9' ARE alphanumeric and must not be skipped.
• Not converting to lowercase before comparing ('A' != 'a').
• Empty string edge case: an empty string after cleaning is a valid palindrome — return true.

Approach 3: Optimized Two-Pointer

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

valid_palindrome_optimized.py

"""
Solution for Valid Palindrome
"""

def solve():
    """Implementation for approach 3 of Valid Palindrome"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

valid_palindrome_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Valid Palindrome
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

ValidPalindromeOptimized.java

/**
 * Solution for Valid Palindrome
 * Approach 3
 */
public class ValidPalindromeOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

valid_palindrome_optimized.js

/**
 * Solution for Valid Palindrome
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

valid_palindrome_optimized.rs

/// Solution for Valid Palindrome
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

valid_palindrome_optimized.go

package main

import "fmt"

// Solution for Valid Palindrome
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Related Problems

• Palindrome Number ↗ Easy #9
• Palindrome Linked List ↗ Easy #234
• Longest Palindromic Substring ↗ Medium #5

Interview Tips

Key points to discuss

• Clarify “alphanumeric” immediately — it includes digits, not just letters.
• Lead with the two-pointer approach (O(1) space) — it is the expected answer in most interviews.
• The clean-then-check approach is fine as a first step to understand the problem before optimizing to O(1) space.

← Previous
#124 Binary Tree Maximum Path Sum Next
#127 Word Ladder →