Valid Palindrome

Problem#

Return true if, after lowercasing and removing all non-alphanumeric characters, the string equals its reverse.

Examples#

"A man, a plan, a canal: Panama" → true (becomes "amanaplanacanalpanama")
"race a car" → false ("raceacar")
" " → true (empty)

Constraints#

1 <= s.length <= 2 * 10^5, ASCII.

Hints#

Hint 1

Skip junk characters in-place rather than building a cleaned copy.

Hint 2

Two pointers walking inward; compare lowercased letters/digits only.

Approach#

Filter then compare — O(n) space for the cleaned string.

Two pointers in place — advance each pointer past non-alphanumerics, then compare. O(1) space.

Solution#

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

func isPalindrome(s string) bool {
    isAlnum := func(c byte) bool {
        return (c >= '0' && c <= '9') || (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')
    }
    toLower := func(c byte) byte {
        if c >= 'A' && c <= 'Z' {
            return c + 32
        }
        return c
    }
    l, r := 0, len(s)-1
    for l < r {
        for l < r && !isAlnum(s[l]) {
            l++
        }
        for l < r && !isAlnum(s[r]) {
            r--
        }
        if toLower(s[l]) != toLower(s[r]) {
            return false
        }
        l++
        r--
    }
    return true
}

class Solution:
    def isPalindrome(self, s: str) -> bool:
        l, r = 0, len(s) - 1
        while l < r:
            while l < r and not s[l].isalnum():
                l += 1
            while l < r and not s[r].isalnum():
                r -= 1
            if s[l].lower() != s[r].lower():
                return False
            l += 1
            r -= 1
        return True

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

class Solution {
    public 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;
    }
}

function isPalindrome(s: string): boolean {
    const isAlnum = (c: string): boolean => /[a-zA-Z0-9]/.test(c);
    let l = 0, r = s.length - 1;
    while (l < r) {
        while (l < r && !isAlnum(s[l])) l++;
        while (l < r && !isAlnum(s[r])) r--;
        if (s[l].toLowerCase() !== s[r].toLowerCase()) return false;
        l++;
        r--;
    }
    return true;
}

Editorial#

Both pointers are responsible for their own skip logic — that keeps the comparison branch simple. Casting to unsigned char before isalnum/tolower avoids undefined behavior on signed-char platforms when the input contains bytes ≥ 0x80. The l < r guard in the inner skips protects against a string that is entirely punctuation (we’d otherwise walk off the ends).

Complexity#

Time: O(n) — each index advances at most once.
Space: O(1).

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#