Valid Palindrome

easyTwo Pointers88 stepsJava · Python · C++

Check whether a string reads the same both ways after dropping non-alphanumeric characters and ignoring case. Put one pointer at each end, skip characters that don't count, compare, and move inward.

▶ Watch the animated trace

Traced input: s = "A man, a plan, a canal: Panama" → true. Original problem: neetcode.io/problems/is-palindrome

Complexity

BestO(1)

AverageO(n)

WorstO(n)

SpaceO(1)

Best case is a mismatch on the first comparison. No cleaned copy of the string is built.

Key idea

A palindrome mirrors around its centre, so compare s[l] with s[r] and move both inward.
Skip punctuation and spaces in place instead of building a filtered string.
Lower-case both characters before comparing.
Keep l < r in the inner skip loops so the pointers never cross.

Common mistakes

Building a cleaned string uses O(n) extra space; the interviewer may ask for O(1).
Dropping the l < r guard in the skip loops runs off the end on strings like ".,".
Character.isLetter misses digits; the problem counts digits too.

Solution

Java

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;
}

Python

def isPalindrome(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

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(s[l]) != tolower(s[r])) {
            return false;
        }
        l++;
        r--;
    }
    return true;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Not a palindrome After cleaning it's "raceacar"; 'e' and 'a' mismatch.	`s = "race a car"`	`false`
Only punctuation Nothing to compare, so it counts as a palindrome.	`s = " .,"`	`true`
Digits matter '0' and 'p' differ; digits are not skipped.	`s = "0P"`	`false`
Single character `l == r` from the start, so the loop never runs.	`s = "a"`	`true`
Mixed case 'A' and 'a' match after lower-casing.	`s = "Aba"`	`true`