Skip to main content
CodePeetCodePeet
CodePeet 250

Valid Palindrome

EASYProblemSolveExternal Links

Description

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.

Note that when checking whether a string is a palindrome, only alphanumeric characters matter — spaces, punctuation, and other special characters are ignored. Also, the comparison is case-insensitive: 'A' is treated the same as 'a'.

Examples

Example 1

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

Output: true

Explanation: After converting to lowercase and removing non-alphanumeric characters, the string becomes "amanaplanacanalpanama". Reading this forward and backward gives the same string, so it is a palindrome.

Example 2

Input: s = "race a car"

Output: false

Explanation: After processing, the string becomes "raceacar". Reading forward: "raceacar". Reading backward: "racaecar". They are not the same, so it is not a palindrome. Specifically, the 4th character from the left is 'e' but the 4th character from the right is 'a'.

Example 3

Input: s = " "

Output: true

Explanation: After removing non-alphanumeric characters, s becomes an empty string "". An empty string reads the same forward and backward (vacuously true), so it is a palindrome.

Constraints

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

Editorial

Brute Force

Intuition

The most direct approach is to do exactly what the problem says: first build a new "cleaned" string by filtering out all non-alphanumeric characters and converting everything to lowercase. Then reverse this cleaned string and check if it equals the original cleaned string.

Think of it like reading a sentence on a banner. You first copy down only the letters and digits (ignoring spaces and punctuation), all in lowercase. Then you write that same sequence backward on another piece of paper. If the two pieces of paper match, the original phrase is a palindrome.

This approach is simple and correct, but it uses extra space proportional to the length of the string because we create the filtered version and its reverse.

Step-by-Step Explanation

Let's trace through with s = "A man, a plan, a canal: Panama":

Step 1: Iterate through the string. For each character, check if it is alphanumeric. If yes, convert to lowercase and append to a new string called filtered.

Step 2: Processing each character:

  • 'A' → alphanumeric → append 'a'
  • ' ' → not alphanumeric → skip
  • 'm' → alphanumeric → append 'm'
  • 'a' → alphanumeric → append 'a'
  • 'n' → alphanumeric → append 'n'
  • ... (continuing through all characters)
  • Result: filtered = "amanaplanacanalpanama"

Step 3: Create a reversed copy of filtered: reversed = "amanaplanacanalpanama"

Step 4: Compare filtered with reversed: "amanaplanacanalpanama" == "amanaplanacanalpanama" → true.

Step 5: Return true — the string is a palindrome.

Brute Force — Filter, Reverse, and Compare — Watch how we build a cleaned string, reverse it, and then compare the two character by character.

Algorithm

  1. Create an empty string filtered
  2. For each character c in s:
    a. If c is alphanumeric, convert to lowercase and append to filtered
  3. Create reversed = reverse of filtered
  4. Return filtered == reversed

Code

class Solution {
public:
    bool isPalindrome(string s) {
        string filtered;
        for (char c : s) {
            if (isalnum(c)) {
                filtered += tolower(c);
            }
        }
        string reversed = filtered;
        reverse(reversed.begin(), reversed.end());
        return filtered == reversed;
    }
};
class Solution:
    def isPalindrome(self, s: str) -> bool:
        filtered = ''.join(c.lower() for c in s if c.isalnum())
        return filtered == filtered[::-1]
class Solution {
    public boolean isPalindrome(String s) {
        StringBuilder filtered = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (Character.isLetterOrDigit(c)) {
                filtered.append(Character.toLowerCase(c));
            }
        }
        String original = filtered.toString();
        String reversed = filtered.reverse().toString();
        return original.equals(reversed);
    }
}

Complexity Analysis

Time Complexity: O(n)

We iterate through the string once to build the filtered string — O(n). Reversing the filtered string is O(n). Comparing the two strings is O(n). Total: O(n).

Space Complexity: O(n)

We create the filtered string which can be up to length n (if all characters are alphanumeric). We also create the reversed copy of the same length. Total additional space: O(n).

Why This Approach Is Not Efficient

While the brute force approach runs in O(n) time (which is already optimal since we must read every character), it uses O(n) extra space to store the filtered string and its reverse. For a string of length 2 × 10^5, this means allocating up to 400KB of additional memory.

We can do better on space. The key observation is that we don't need to physically build the cleaned string at all. Instead, we can use two pointers — one starting from the left end and one from the right end of the original string. Each pointer skips over non-alphanumeric characters, and we compare the alphanumeric characters they land on. If all matching pairs are equal, it's a palindrome. This eliminates the need for any extra string storage, reducing space to O(1).

Optimal Approach - Two Pointers

Intuition

A palindrome reads the same from both ends. Instead of building a cleaned copy, we can check in-place by using two pointers converging toward the center.

Imagine two people reading the same banner — one from the left and one from the right. Both readers skip over spaces and punctuation, and they ignore case. After each step, they tell each other which letter they're on. If the letters always match until the two readers meet in the middle, the banner is a palindrome.

The left pointer starts at index 0 and moves right. The right pointer starts at the last index and moves left. At each step:

  • Move the left pointer right until it points to an alphanumeric character
  • Move the right pointer left until it points to an alphanumeric character
  • Compare the two characters (case-insensitively)
  • If they differ, return false immediately
  • If they match, move both pointers inward and repeat

If the pointers cross without finding a mismatch, the string is a palindrome. This approach uses no extra space beyond two integer variables.

Step-by-Step Explanation

Let's trace through with s = "A man, a plan, a canal: Panama":

Step 1: Initialize left = 0, right = 29 (last index).

Step 2: left → 'A' (alphanumeric). right → 'a' (alphanumeric). Compare: tolower('A') = 'a' == 'a'. Match! Move left to 1, right to 28.

Step 3: left = 1 → ' ' (not alphanumeric), skip to 2 → 'm'. right = 28 → 'm'. Compare: 'm' == 'm'. Match! Move inward.

Step 4: Continue this process. left skips spaces and punctuation, right skips spaces and punctuation. At each meeting, the alphanumeric characters match:

  • 'a' == 'a' ✓
  • 'n' == 'n' ✓
  • 'a' == 'a' ✓
  • 'p' == 'p' ✓
  • 'l' == 'l' ✓
  • 'a' == 'a' ✓
  • 'n' == 'n' ✓
  • 'a' == 'a' ✓
  • 'c' == 'c' ✓

Step 5: Eventually left >= right (pointers cross). No mismatch found. Return true.

Two Pointers — In-Place Palindrome Check — Watch how two pointers converge from both ends, skipping non-alphanumeric characters and comparing matching pairs.

Algorithm

  1. Initialize left = 0, right = s.length - 1
  2. While left < right:
    a. While left < right and s[left] is not alphanumeric, increment left
    b. While left < right and s[right] is not alphanumeric, decrement right
    c. If tolower(s[left]) ≠ tolower(s[right]), return false
    d. Increment left, decrement right
  3. Return true (all matching pairs checked, no mismatch found)

Code

class Solution {
public:
    bool isPalindrome(string s) {
        int left = 0, right = s.size() - 1;
        while (left < right) {
            // Skip non-alphanumeric from left
            while (left < right && !isalnum(s[left])) left++;
            // Skip non-alphanumeric from right
            while (left < right && !isalnum(s[right])) right--;
            // Compare characters (case-insensitive)
            if (tolower(s[left]) != tolower(s[right])) return false;
            left++;
            right--;
        }
        return true;
    }
};
class Solution:
    def isPalindrome(self, s: str) -> bool:
        left, right = 0, len(s) - 1
        while left < right:
            # Skip non-alphanumeric from left
            while left < right and not s[left].isalnum():
                left += 1
            # Skip non-alphanumeric from right
            while left < right and not s[right].isalnum():
                right -= 1
            # Compare characters (case-insensitive)
            if s[left].lower() != s[right].lower():
                return False
            left += 1
            right -= 1
        return True
class Solution {
    public boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            // Skip non-alphanumeric from left
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) left++;
            // Skip non-alphanumeric from right
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) right--;
            // Compare characters (case-insensitive)
            if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

Complexity Analysis

Time Complexity: O(n)

Each pointer traverses at most n positions total. The left pointer only moves right, and the right pointer only moves left. Combined, they visit each character at most once. The total number of operations is at most n.

Space Complexity: O(1)

We use only two integer variables (left and right) regardless of the input size. No additional strings, arrays, or data structures are created. This is a significant improvement over the brute force approach which used O(n) extra space.