Solution: Valid Palindrome

Statement

Given a string, s, return TRUE if it is a palindrome; otherwise, return FALSE.

A phrase is considered a palindrome if it reads the same backward as forward after converting all uppercase letters to lowercase and removing any characters that are not letters or numbers. Only alphanumeric characters (letters and digits) are taken into account.

Constraints:

• $1 \leq$ s.length $\leq 3000$

• s consists only of printable ASCII characters.

Solution

So far, you‘ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

A naive approach to checking if a string is a palindrome would involve first removing all non-alphanumeric characters and converting the string to lowercase for case-insensitive comparison. This can be done by iterating the string once and appending only letters and digits to a new cleaned string. Once the cleaned version of the string is obtained, we can reverse it and compare it to the original cleaned string. If both versions are identical, the string is a palindrome; otherwise, it is not.

While simple to implement, this method requires extra space to store the cleaned string and its reversed copy, leading to a space complexity of $O(n)$. This extra space usage and unnecessary reversal make the approach less efficient than the two pointer method.

Optimized approach using two pointers

The two pointer approach minimizes unnecessary computations and extra space. It begins by initializing two pointers: one at the start (left) and one at the end (right) of the string. These pointers move inward simultaneously, ensuring an optimized traversal. As the algorithm processes the string, it skips spaces, punctuation, and special characters, focusing only on valid alphanumeric characters (letters and digits). This ensures that formatting and symbols do not affect the palindrome check. To handle case differences, all letter comparisons are case-insensitive, converting characters to lowercase before evaluation.

The algorithm compares the characters at the left and right pointers at each step. If they match, both pointers move inward to check the next pair. If a mismatch is found, immediately return FALSE, indicating the string is not a palindrome. The process continues until the pointers meet or cross each other, at which point, if no mismatches are found, return TRUE, confirming the string is a valid palindrome. The two pointer approach allows us to solve this problem in $O(n)$ time complexity while using $O(1)$ extra space, making it highly efficient.

In the following section, we will gradually build the solution. Alternatively, you can skip straight to just the code.