Valid Palindrome

A valid palindrome is a string that is the same when read forward or backward, ignoring spaces, punctuation, and case. You need to write a function that takes a string as input and returns true if it is a valid palindrome and false otherwise.

The official definition of a palindrome does not universally specify whether spaces, punctuation, or letter case should be considered. The definition of a palindrome typically focuses on the sequence of characters and whether it reads the same forwards and backwards.

This definition emphasizes the symmetry of the characters in a sequence, irrespective of spaces, punctuation, or letter case. In practice, people often apply this definition while ignoring spaces, punctuation, and letter case, as it aligns with common usage and makes the concept of palindromes more versatile.

However, it’s important to note that in specific contexts, especially in technical or linguistic discussions, the treatment of spaces, punctuation, and letter case may be explicitly defined.

For example, “racecar” and “Madam, I’m Adam” are valid palindromes.

The choice of method depends on the specific requirements and constraints of your problem, as well as the programming language you are using. The two-pointer approach is one of the most commonly used methods due to its simplicity and efficiency. However, other methods may be preferred in certain contexts or when additional preprocessing is needed.

Using two pointers

To solve this problem using the two-pointer technique, you can have two pointers, one starting from the beginning of the string and the other from the end. Then, you compare characters at these pointers while ignoring non-alphanumeric characters and considering characters as case-insensitive.

#include <cassert>
#include <cctype>
#include <iostream>
#include <string>

using namespace std;

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

  while (left < right) {
    // Skip non-alphanumeric characters from the left
    while (left < right && !isalnum(s[left])) {
      left++;
    }

    // Skip non-alphanumeric characters from the right
    while (left < right && !isalnum(s[right])) {
      right--;
    }

    // Convert characters to lowercase for case-insensitive comparison
    char leftChar = tolower(s[left]);
    char rightChar = tolower(s[right]);

    // Compare characters
    if (leftChar != rightChar) {
      return false;
    }

    left++;
    right--;
  }

  return true;
}

int main() {
  assert(isPalindrome("A man, a plan, a canal: Panama") == true);
  assert(isPalindrome("race a car") == false);
  assert(isPalindrome("") == true);
  assert(isPalindrome("ab") == false);

  cout << "All tests passed!" << endl;
  return 0;
}

The time complexity of this algorithm is O(n), where n is the length of the input string. Both pointers traverse the string once, and the operations at each step (skipping non-alphanumeric characters and comparing characters) are constant time. The space complexity is O(1).

Other solutions

• Using string reversal: Reverse the given string and check if it is the same as the original string. This method is straightforward but may not be efficient in terms of time complexity, especially for very long strings.
• Using regular expressions: Use regular expressions to remove spaces, punctuation, and convert the string to lowercase (or uppercase) and then compare it with its reverse to check if it is a palindrome. Regular expressions can help with the preprocessing step.
• Using recursion: The base case would involve checking if the first and last characters are the same, and then recursively checking the substring between them. This approach can be less efficient due to the overhead of recursive function calls.
• Using stack or queue: Push the characters onto the stack or enqueue them into a queue while ignoring spaces and punctuation, and then pop or dequeue characters from the other end and compare them.
• Using in-place character comparison: For languages that allow in-place character comparison (e.g., C/C++), you can iterate through the string and compare characters from the beginning and end, ignoring spaces, punctuation, and letter case.