Valid Palindrome (Two Pointer Check)

Problem Statement

Given a string s, return true if it is a palindrome, considering only alphanumeric characters and ignoring letter case. All other characters are skipped.

Example

Input:  s = "A man, a plan, a canal: Panama"
Output: true
Explanation: After filtering -> "amanaplanacanalpanama", which reads the same both ways.

Two Pointer Approach

Use one pointer at the start and one at the end. Skip any character that is not a letter or digit, then compare the two characters in lower case.

• Move left forward while it points at a non-alphanumeric character.
• Move right backward while it points at a non-alphanumeric character.
• Compare s[left] and s[right] in lower case; if they differ, it is not a palindrome.
• Step both pointers inward and repeat until they cross.

Complexity

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

Solution Code

Python

def isPalindrome(s):
    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

Java

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

C++

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

Key Takeaways

• Two pointers avoid building a filtered copy, keeping space at O(1).
• Always guard the inner skip loops with left < right to avoid overshooting.
• This "converge from both ends" pattern is the classic opposite-direction two pointer.