Valid Palindrome

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. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

Constraints

• 1 <= s.length <= 2 * 105
• s consists only of printable ASCII characters.

Solution

The problem Valid Palindrome can be solved using a sliding window technique. First, leftmost index can be gained by sliding the index to the right until an alphanumeric character is found. Next, rightmost index can be gained by sliding the index to the left until an alphanumeric character is found. If characters from 2 indexes are not identical, the given string is not a palindrome. If the process is repeated and leftmost index exceeds rightmost index, the given string is a palindrome.

Implementation

class Solution
{
  public:
    bool isalnum(char ch) { return ('a' <= ch && ch <= 'z') || ('A' <= ch && ch <= 'Z') || ('0' <= ch && ch <= '9'); }
    char tolower(char ch)
    {
        if ('A' <= ch && ch <= 'Z')
            ch -= 'A' - 'a';
        return ch;
    }

    bool isPalindrome(string s)
    {
        int left = -1, right = s.length();

        while (true)
        {
            while (++left < s.length())
                if (isalnum(s[left]))
                    break;

            while (0 <= --right)
                if (isalnum(s[right]))
                    break;

            if (right <= left)
                return true;

            if (tolower(s[left]) != tolower(s[right]))
                return false;
        }
    }
};