Problem statement

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, 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.

Constraints

• 0 <= s.length <= 40
• s consists of printable ASCII characters.

Hints for Valid Palindrome

1. Hint 1

   Normalize first: lowercase and strip everything that is not a letter or digit.

2. Hint 2

   Two pointers from both ends avoid building the reversed copy.

How to solve Valid Palindrome

Do not build a cleaned copy of the string — walk it from both ends at once and simply skip anything that is not alphanumeric. Compare the surviving characters case-insensitively; the first mismatch settles it.

Approach

1. Put l at the start and r at the end.
2. Advance l rightwards past any non-alphanumeric character, and r leftwards likewise.
3. Compare the two characters after lowercasing; a mismatch means it is not a palindrome.
4. Move both pointers inward and repeat until they meet.

Why it works

Filtering and lowercasing are per-character decisions, so they can be applied on the fly rather than in a separate pass — which is what keeps the extra space constant. The two-pointer comparison is exactly the definition of a palindrome applied to the filtered sequence: position i from the front must equal position i from the back, and the skipping ensures both pointers always land on characters that survive the filter.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• Keep the skip loops bounded by l < r, or a string of only punctuation runs off the end.
• Digits count as alphanumeric, not just letters.
• Lowercase both sides before comparing.
• An empty string, or one with no alphanumeric characters at all, is a palindrome.

Reference solution

Python

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

Java

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

C++

bool isPalindrome(string s) {
    int l = 0, r = (int) s.size() - 1;
    while (l < r) {
        while (l < r && !isalnum((unsigned char) s[l])) l++;
        while (l < r && !isalnum((unsigned char) s[r])) r--;
        if (tolower((unsigned char) s[l]) != tolower((unsigned char) s[r])) return false;
        l++;
        r--;
    }
    return true;
}

JavaScript

var isPalindrome = function(s) {
    const c = s.toLowerCase().replace(/[^a-z0-9]/g, "");
    for (let i = 0, j = c.length - 1; i < j; i++, j--) {
        if (c[i] !== c[j]) return false;
    }
    return true;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Binary Tree Paths Easy
• Find Most Frequent Vowel and Consonant Easy
• Maximum Difference Between Even and Odd Frequency I Easy
• Find Valid Pair of Adjacent Digits in String Easy
• Count the Number of Special Characters I Easy
• Find Maximum Number of String Pairs Easy