Valid Palindrome

Approach Summary

Two pointers from both ends. Skip non-alphanumeric characters. Compare lowercased characters.

Full Solution & Approach

A palindrome reads the same forward and backward, so the natural strategy is to compare characters from both ends and work inward. The two twists in this problem are that non-alphanumeric characters must be skipped and the comparison must be case-insensitive. Two pointers start at the two ends: left at index 0 and right at the last index. Each iteration first advances left past any character that is not a letter or digit, and similarly moves right backward past such characters — this handles strings like "A man, a plan, a canal: Panama" where punctuation and spaces sit between the characters we actually compare. Only then do we compare the two characters, lower-casing both sides so "A" and "a" are treated as equal. If they differ, the string is not a palindrome and we return false immediately. If they match, move both pointers one step inward and repeat. If the pointers meet or cross, every mirrored pair matched, so the string is a palindrome and we return true. A single character or an empty string trivially passes because the loop never finds a mismatched pair. This approach never builds a cleaned copy of the string, so it runs in O(n) time while using only O(1) extra space — the standard two-pointer technique that interviewers expect.

Each character is visited at most twice total (once by each pointer in the worst case) — O(n) time. Only two index variables, so O(1) space.

Solution Code

Solution

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

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

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

bool isPalindrome(const string& s) {
    int left = 0, right = (int)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;
}

Edge Cases to Watch

Empty string or a string of only punctuation — true
Mixed case — handled by lower-casing each side
Alphanumeric mix like "0P" — 0 is not P, false
Single character — true

How to Recognize This Pattern

Palindrome check with special characters

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(1)