Back to solutions

Valid Palindrome

EasyTwo Pointers

Return true if the string is a palindrome when considering only alphanumeric characters and ignoring case.

Open problem
Constraints
  • 1 <= s.length <= 2 * 10^5
  • s consists of printable ASCII characters

Two pointers skipping non-alphanumerics

Time O(n)Space O(1)

Move a pointer from each end toward the centre, skipping characters that are not letters or digits, and compare lowercase forms. A mismatch means it is not a palindrome.

#include <bits/stdc++.h>
using namespace std;

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