125_valid_palindrome.cpp

/*
LeetCode 125 - Valid Palindrome
Difficulty: Easy

Problem:
A phrase is a palindrome if, after converting all uppercase letters into lowercase letters
and removing all non-alphanumeric characters, it reads the same forward and backward.
Given a string s, return true if it is a palindrome, or false otherwise.

Example 1:
    Input: s = "A man, a plan, a canal: Panama"
    Output: true

Example 2:
    Input: s = "race a car"
    Output: false

Example 3:
    Input: s = " "
    Output: true

Constraints:
    1 <= s.length <= 2 * 10^5
    s consists only of printable ASCII characters.

Time Complexity: O(n)
Space Complexity: O(1)
*/

#include <iostream>
#include <string>
#include <cctype>

using namespace std;

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

int main() {
    Solution solution;

    cout << (solution.isPalindrome("A man, a plan, a canal: Panama") ? "true" : "false") << endl; // true
    cout << (solution.isPalindrome("race a car") ? "true" : "false") << endl;                      // false
    cout << (solution.isPalindrome(" ") ? "true" : "false") << endl;                               // true

    return 0;
}