Valid Palindrome

Problem Statement

In the given task, we need to determine if a string, referred to as s, qualifies as a palindrome after undergoing specific transformations. A palindrome is a sequence that reads the same backward as forward. For the purposes of this task, the transformations involve converting all uppercase letters to lowercase and removing all non-alphanumeric characters, which includes anything other than letters and numbers. The output will be true if the modified string is a palindrome, and false otherwise.

Examples

Example 1

Input:

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

Output:

true

Explanation:

"amanaplanacanalpanama" is a palindrome.

Example 2

Input:

s = "race a car"

Output:

false

Explanation:

"raceacar" is not a palindrome.

Example 3

Input:

s = " "

Output:

true

Explanation:

s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.

Constraints

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

Approach and Intuition

To solve this problem, let's break down the examples provided and extract the intuition and methodology we can use:

1. Convert all uppercase characters in the string to lowercase. This ensures that the comparison is case-insensitive, treating 'A' and 'a' as equivalent.
2. Remove all non-alphanumeric characters. This step requires scanning each character in the string and excluding any that are not letters or numbers.
3. Check if the resulting string is a palindrome. This can be done by comparing the string to its reverse; if they are the same, the string is a palindrome.

Based on each example:

• Example 1: Clearing all characters that are not alphanumeric and converting the rest to lower case provides a straightforward, long palindrome.
• Example 2: Even after cleaning the input string, the sequence does not read the same forwards and backwards, indicating it isn't a palindrome.
• Example 3: A string composed entirely of spaces results in an empty string after cleaning. Since an empty string trivially reads the same in both directions, it is considered a palindrome.

With these steps and considerations in mind, the implementation can systematically check any input string for its palindrome status post-transformation.

Solutions

class Solution {
public:
    bool checkPalindrome(string str) {
        for (int start = 0, end = str.length() - 1; start < end; start++, end--) {
            while (start < end && !isalnum(str[start])) start++;
            while (start < end && !isalnum(str[end])) end--;
    
            if (tolower(str[start]) != tolower(str[end])) return false;
        }
    
        return true;
    }
};