Valid Palindrome

easy
Two PointersStringTwo Pointers

Given a string s, determine if it is a palindrome considering only alphanumeric characters and ignoring cases. 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.

Return true if the string is a valid palindrome, and false otherwise.

Examples

Example 1

  • Input: s = "A man, a plan, a canal: Panama"
  • Output: true
  • Explanation: After removing non-alphanumeric characters and converting to lowercase, the string becomes "amanaplanacanalpanama", which is a palindrome.

Example 2

  • Input: s = "race a car"
  • Output: false
  • Explanation: After processing, the string becomes "raceacar", which is not a palindrome.

Example 3

  • Input: s = " "
  • Output: true
  • Explanation: After removing non-alphanumeric characters, the string is empty. An empty string is considered a palindrome.

Constraints

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

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Filter and Reverse

Intuition

A straightforward approach is to first build a cleaned version of the string containing only lowercase alphanumeric characters, then check if this cleaned string equals its reverse. This uses extra space to store the filtered string but is easy to understand and implement.

Algorithm

  1. Iterate through the string and keep only alphanumeric characters, converting each to lowercase.
  2. Build a new cleaned string from these characters.
  3. Reverse the cleaned string.
  4. Compare the cleaned string with its reversed version.
  5. Return true if they are equal, false otherwise.
TimeO(n)SpaceO(n)

Code (C++ · Java · Python · Go)

C++17
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 21
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 reversed = cleaned.reverse().toString();
        return forward.equals(reversed);
    }
}
Python 3.12
def isPalindrome(s: str) -> bool:
    cleaned = "".join(c.lower() for c in s if c.isalnum())
    return cleaned == cleaned[::-1]
Go 1.26
import (
    "strings"
    "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))
        }
    }

    reversed := make([]rune, len(cleaned))
    for i, c := range cleaned {
        reversed[len(cleaned)-1-i] = c
    }

    return string(cleaned) == string(reversed)
}
Approach 2

Two Pointers

Intuition

Instead of creating a new string, we can check the palindrome property in-place using two pointers. One pointer starts at the beginning and the other at the end. Both pointers skip non-alphanumeric characters and compare the remaining characters in a case-insensitive manner. This avoids allocating extra memory for a filtered string.

Algorithm

  1. Initialize a left pointer at the start and a right pointer at the end of the string.
  2. Move the left pointer forward while it points to a non-alphanumeric character.
  3. Move the right pointer backward while it points to a non-alphanumeric character.
  4. Compare the lowercase versions of the characters at both pointers.
  5. If they differ, return false. Otherwise, move both pointers inward and repeat.
  6. If the pointers cross without finding a mismatch, return true.
TimeO(n)SpaceO(1)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    bool isPalindrome(string s) {
        int left = 0, right = 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 21
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;
    }
}
Python 3.12
def isPalindrome(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
Go 1.26
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
}

Frequently asked questions

What is the optimal time complexity of Valid Palindrome?

The most efficient approach in this guide ("Two Pointers") runs in O(n) time and uses O(1) extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Valid Palindrome use?

Valid Palindrome is a easy-level Two Pointers problem involving String, Two Pointers. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Valid Palindrome be solved without extra space?

The most space-efficient approach in this guide uses O(1) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(n), while the optimized version uses O(1).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Original problem: leetcode.com

Loading editor...
Input
s=
"A man, a plan, a canal: Panama"
Expected Output
true