C++: Valid Palindrome

Thought Process

To determine if a string is a valid palindrome, we first preprocess the string by removing all non-alphanumeric characters and converting it to lowercase. This ensures the comparison is case-insensitive and ignores special characters. We then use a two-pointer approach to compare characters from the beginning and end of the string, moving towards the center. If all corresponding characters match, the string is a palindrome; otherwise, it is not. 

class Solution {
public:
    bool isPalindrome(string s) {
        
        string str;
        for(int i=0;i<s.size();i++){
            char ch = s[i];
            if(isalnum(ch)){
                str.push_back(tolower(ch));
            }
        }
        int n = str.size();
        for(int i=0;i<n/2;i++){
            if(str[i]!=str[n-1-i])
                return false;
        }
        return true;

    }
};

Code Complexity

Time Complexity: O(n)

The algorithm iterates through the string twice: once for preprocessing and once for comparison, making it linear in time complexity.

Space Complexity: O(n)

The algorithm uses additional space to store the preprocessed string, where n is the length of the input string.

Code copied!