Link to Question

EASY

125. Valid Palindrome

Given a string s, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Example

Input:

s = "A man, a plan, a canal: Panama"

Output:

true

Explanation: "amanaplanacanalpanama" is a palindrome.

---

Constraints

• 1 ≤ s.length ≤ 2 × 10⁵
• s consists only of printable ASCII characters.

---

Solution: Two Pointers

• Time Complexity: O(n), where n is the length of the string.
• Space Complexity: O(1), ignoring the space for input and output.

C++

class Solution {
public:
    bool isPalindrome(string s) {
        int left = 0, right = 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;
    }
};