Valid Palindrome: Exploring Different Approaches

A palindrome is a phrase or sequence of characters that reads the same forward and backwards, ignoring non-alphanumeric characters and considering case-insensitivity. In this blog post, we will explore two different approaches to determine if a given string is a valid palindrome.

Problem Statement

Given a string s, we need to determine if it is a valid palindrome. To do this, we must convert all uppercase letters to lowercase, remove all non-alphanumeric characters, and check if the resulting string reads the same forward and backwards. If it does, we return true; otherwise, we return false.

Approach 1: Two-Pointer Approach

Our first approach involves using a two-pointer technique. We initialize two pointers, left and right, pointing to the beginning and end of the string, respectively. We increment the first pointer and decrement the second pointer until they meet in the middle. During this process, we compare the characters at each pointer position, ignoring non-alphanumeric characters.

Here's the step-by-step algorithm:

1. Initialize two pointers, left and right, pointing to the beginning and end of the string, respectively.

2. While left < right, do the following:

   • If the characters at left and right positions are non-alphanumeric, increment left or decrement right accordingly.

   • If both characters are alphanumeric, compare them ignoring case sensitivity:

     • If they are equal, increment left and decrement right.

     • If they are not equal, return false as the string is not a palindrome.

3. If the loop completes without returning false, it means the string is a valid palindrome. Return true.

The code for this approach looks like this:

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

    while (left < right) {
        while (left < right && !isalnum(s[left])) {
            left++;
        }
        while (left < right && !isalnum(s[right])) {
            right--;
        }

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

        left++;
        right--;
    }

    return true;
}

Approach 2: String Manipulation and Reversal

Our second approach involves manipulating the string by converting all uppercase letters to lowercase, removing non-alphanumeric characters, and then comparing the string with its reversed version.

Here's the step-by-step algorithm:

1. Create an empty string s1 to store the modified version of the input string.

2. Iterate over each character ele in the input string s:

   • If ele is alphanumeric:

     • If ele is uppercase, convert it to lowercase and append it to s1.

     • If ele is not uppercase, append it to s1 as it is.

3. Create a string reversed by reversing the characters in s1.

4. Compare s1 with reversed:

   • If they are equal, return true as the string is a valid palindrome.

   • If they are not equal, return false as the string is not a palindrome.

The code for this approach is as follows:

bool isPalindrome(string s)
{
    string s1;
    for (auto ele : s)
    {
        if (isalnum(ele))
        {
            if (isupper(ele))
            {
                s1.push_back(tolower(ele));
            }
            else
            {
                s1.push_back(ele);
            }
        }
    }
    string reversed = s1;
    reverse(reversed.begin(), reversed.end());
    return s1 == reversed;
}

Complexity Analysis

Approach 1: Using Two Pointers

• Time Complexity: The time complexity of this approach is O(n), where n is the length of the input string. We traverse the string once from both ends using the two pointers, and each iteration takes constant time.

• Space Complexity: The space complexity is O(1) since we only use a constant amount of extra space for the two pointers and temporary variables.

Approach 2: Using String Reversal

• Time Complexity: The time complexity of this approach is O(n), where n is the length of the input string. Creating the modified string takes O(n) time as we iterate through the original string once. Reversing the string also takes O(n) time.

• Space Complexity: The space complexity is O(n) since we need additional space to store the modified string and its reversed version. In the worst case, the modified string can be the same length as the input string.

Conclusion

In this blog post, we explored two approaches to check if a given string is a valid palindrome. The first approach utilized two pointers to compare characters from the beginning and end of the string, while the second approach involved creating a modified string and checking if it is equal to its reversed version. Both approaches offer efficient ways to validate palindromic strings in C++. You can choose the approach that suits your requirements and implement it in your projects.

Remember, when working with string manipulation and comparisons, it is essential to consider edge cases and constraints provided in the problem statement.