Valid Palindrome easy

Problem Statement

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forwards and backwards. Alphanumeric characters include letters and numbers.

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 Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:

Input: s = "race a car" Output: true Explanation: "raceacar" is a palindrome.

Steps

1. Preprocessing: Convert the input string to lowercase and remove all non-alphanumeric characters. This simplifies the palindrome check.

2. Two Pointers: Use two pointers, one at the beginning and one at the end of the processed string.

3. Comparison: Compare the characters at the two pointers. If they are different, the string is not a palindrome.

4. Iteration: Move the left pointer to the right and the right pointer to the left, repeating step 3 until the pointers cross.

5. Result: If all character comparisons pass, the string is a palindrome; otherwise, it's not.

Explanation

The core idea is to efficiently check if a string is a palindrome after cleaning it of irrelevant characters. Using two pointers avoids unnecessary iterations and provides a linear time solution. The preprocessing step ensures that only alphanumeric characters are considered, making the comparison straightforward.

Code

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

using namespace std;

bool isPalindrome(string s) {
    // Preprocessing: Convert to lowercase and remove non-alphanumeric characters
    string clean_s = "";
    for (char c : s) {
        if (isalnum(c)) {
            clean_s += tolower(c);
        }
    }

    // Two-pointer approach
    int left = 0;
    int right = clean_s.length() - 1;
    while (left < right) {
        if (clean_s[left] != clean_s[right]) {
            return false; // Not a palindrome
        }
        left++;
        right--;
    }

    return true; // It's a palindrome
}

int main() {
    string s1 = "A man, a plan, a canal: Panama";
    string s2 = "race a car";
    string s3 = " ";

    cout << "\"" << s1 << "\" is a palindrome: " << isPalindrome(s1) << endl; // true
    cout << "\"" << s2 << "\" is a palindrome: " << isPalindrome(s2) << endl; // true
    cout << "\"" << s3 << "\" is a palindrome: " << isPalindrome(s3) << endl; // true

    return 0;
}

Complexity

• Time Complexity: O(n), where n is the length of the input string. This is dominated by the preprocessing and two-pointer traversal.
• Space Complexity: O(n) in the worst case, if the input string contains mostly alphanumeric characters. The clean_s string could potentially be as large as the original string. In the best case (mostly non-alphanumeric characters), it could be O(1). However, it's more accurate to consider it O(n) due to potential worst-case scenarios.