Valid Palindrome

How it works

Instead of building a new string, we can check the palindrome directly in-place using two pointers.
One pointer starts at the beginning (l) and the other at the end (r).
We move both pointers inward, skipping any characters that are not letters or digits.
Whenever both pointers point to valid characters, we compare them in lowercase form.
If at any point they differ, the string is not a palindrome.
This method avoids extra space and keeps the logic simple and efficient.

Steps

1. Initialize two pointers:
   • l at the start of the string,
   • r at the end of the string.
2. While l is less than r:
   • Move l forward until it points to an alphanumeric character.
   • Move r backward until it points to an alphanumeric character.
   • Compare the lowercase characters at l and r:
     • If they don't match, return false.
   • Move both pointers inward: l += 1, r -= 1.
3. If the loop finishes without mismatches, return true.

Complexity

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

Things to watch for

Not Skipping Non-Alphanumeric Characters

The problem requires ignoring all characters that are not letters or digits. Forgetting to skip spaces, punctuation, and special characters will cause false negatives. For example, "A man, a plan, a canal: Panama" should be recognized as a palindrome, but including the spaces and punctuation in the comparison will incorrectly return false.

Case Sensitivity

Letters must be compared in a case-insensitive manner. Comparing 'A' directly with 'a' will return false even though they should be treated as equal. Always convert both characters to the same case (lowercase or uppercase) before comparing.

class Solution:
    def isPalindrome(self, s: str) -> bool:
        l, r = 0, len(s) - 1

        while l < r:
            while l < r and not self.alphaNum(s[l]):
                l += 1
            while r > l and not self.alphaNum(s[r]):
                r -= 1
            if s[l].lower() != s[r].lower():
                return False
            l, r = l + 1, r - 1
        return True

    def alphaNum(self, c):
        return (ord('A') <= ord(c) <= ord('Z') or
                ord('a') <= ord(c) <= ord('z') or
                ord('0') <= ord(c) <= ord('9'))

class Solution {
public:
    bool isPalindrome(string s) {
        int l = 0, r = s.length() - 1;

        while (l < r) {
            while (l < r && !alphaNum(s[l])) {
                l++;
            }
            while (r > l && !alphaNum(s[r])) {
                r--;
            }
            if (tolower(s[l]) != tolower(s[r])) {
                return false;
            }
            l++; r--;
        }
        return true;
    }

    bool alphaNum(char c) {
        return (c >= 'A' && c <= 'Z' ||
                c >= 'a' && c <= 'z' ||
                c >= '0' && c <= '9');
    }
};