Valid Palindrome

Problem Description

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.

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

Examples

Constraints

• 1 ≤ s.length ≤ 2 * 10⁵
• s consists only of printable ASCII characters.

Build a Clean String First, Then Check It Backwards

The cleanest code cleans the string into a new one and then compares cleaned == cleaned[::-1]. That uses O(n) space. You can get to O(1) space by working directly on the original string with two pointers, skipping non-alphanumeric characters on the fly. The result is the same, the space cost is not.

Solution 1: Build Cleaned String

Create a new string containing only lowercase alphanumeric characters, then check if it equals its reverse.

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 str = cleaned.toString();
        return str.equals(new StringBuilder(str).reverse().toString());
    }
}

class Solution:
    def isPalindrome(self, s: str) -> bool:
        cleaned = [c.lower() for c in s if c.isalnum()]
        return cleaned == cleaned[::-1]

#include <string>
#include <cctype>
#include <algorithm>

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

Complexity Analysis:

• Time Complexity: O(n). One pass to build, one pass to reverse and compare.
• Space Complexity: O(n). The cleaned string can be up to n characters.

Where it breaks: uses O(n) extra space. The two-pointer approach below eliminates this entirely.

Solution 2: Two Pointers (In-Place, No Extra String)

Place left at the start and right at the end. Skip non-alphanumeric characters from both ends. Compare the lowercase versions of the characters at both pointers. If they ever differ, it’s not a palindrome. If the pointers cross without a mismatch, it is.

class Solution {
    public boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            // advance left past non-alphanumeric characters
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) left++;
            // retreat right past non-alphanumeric characters
            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;
    }
}

class Solution:
    def isPalindrome(self, s: str) -> bool:
        left, right = 0, len(s) - 1
        while left < right:
            # advance left past non-alphanumeric characters
            while left < right and not s[left].isalnum():
                left += 1
            # retreat right past non-alphanumeric characters
            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

#include <string>
#include <cctype>

class Solution {
public:
    bool isPalindrome(std::string s) {
        int left = 0, right = s.size() - 1;
        while (left < right) {
            // advance left past non-alphanumeric characters
            while (left < right && !isalnum(s[left])) left++;
            // retreat right past non-alphanumeric characters
            while (left < right && !isalnum(s[right])) right--;
            if (tolower(s[left]) != tolower(s[right])) return false;
            left++;
            right--;
        }
        return true;
    }
};

Complexity Analysis:

• Time Complexity: O(n). Each character is visited at most once by each pointer.
• Space Complexity: O(1). Two index variables, no extra string allocation.

Where it breaks: the inner while loops must check left < right as their guard. If you only check the outer condition, the pointers can cross each other and you’ll compare wrong characters.

Common Mistakes

• Forgetting to lowercase before comparing. “A” and “a” are not equal without conversion, but they should be treated as the same character.
• Missing the left < right guard inside the inner while loops. Without it, left and right can cross, and you’ll skip the exit condition of the outer loop.
• Treating a single space ” ” as non-palindrome. After stripping non-alphanumeric characters, you get an empty string. An empty string is a valid palindrome.

Frequently Asked Questions

Why is an empty string a palindrome? By convention, a string reads the same forward and backward if there are no characters to differ. This is the same reason the empty product is 1: vacuous truth.

Can you solve this without checking isalnum on every character? You could precompute a cleaned version, but that’s O(n) space. The two-pointer approach with inline isalnum checks is already optimal.

What does this problem test in interviews? Mostly pointer management and handling edge cases from the character filtering. The algorithm itself is simple; the mistakes come from careless inner loop guards.

← All Problems