Valid Palindrome

12 May 2026 0 Likes

Problem Description

Given a string s, return true if it is a palindrome, or false otherwise.

A string is considered a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward.

Alphanumeric characters include: Lowercase letters, Uppercase letters and Digits.
Example 1:
Input: s = "A man, a plan, a canal: Panama"
 Output: true
Explanation: After removing non-alphanumeric characters and converting to lowercase: "amanaplanacanalpanama"

The string reads the same from both directions.
Example 2:
Input: s = "race a car"
 Output: false
Explanation: After processing the string: "raceacar", the string is not the same when reversed.
Example 3:
Input: s = " "
 Output: true
Explanation: After removing non-alphanumeric characters, the string becomes empty. An empty string is considered a valid palindrome.

Constraints

The string may contain:
- Uppercase letters
- Lowercase letters
- Digits
- Spaces
- Special characters

The length of the string may vary depending on platform limits.

The output should be:
true → if the processed string is a palindrome
false → otherwise

An efficient solution is expected to process the string in linear time.

Understanding the Problem

The problem is asking us to check whether a string remains identical when read from left to right and right to left after cleaning the string. The cleaning process involves:

1. Ignoring uppercase and lowercase differences
2. Removing spaces and special characters

For example: "A man, a plan, a canal: Panama"
After processing: "amanaplanacanalpanama"

Now if we compare characters from both ends: a == a, m == m and a == a, all characters continue matching until the middle of the string.

Therefore, the string becomes a valid palindrome. The main challenge is efficiently skipping unnecessary characters while comparing both sides of the string.

Hints

The first hint is to think about comparing characters from both ends of the string simultaneously.

A two-pointer technique can help efficiently traverse the string. One pointer starts from the beginning, while the other starts from the end.

Whenever a character is not alphanumeric, simply skip it.

Before comparison, convert characters into lowercase so that uppercase and lowercase letters are treated equally.

If all valid characters match successfully, the string is a palindrome.

Solutions

OPTIMAL

Two Pointer Palindrome Validation Solution

This approach uses the two-pointer technique to efficiently check whether the string is a valid palindrome.

We maintain:
i → pointer starting from the beginning of the string
j → pointer starting from the end of the string

While traversing the string:

1) If the current character is not alphanumeric, we skip it because special characters and spaces are ignored in palindrome validation.

Before comparison, both characters are converted into lowercase so that uppercase and lowercase letters are treated equally.

2) If the characters do not match, Character.toLowerCase(ci) != Character.toLowerCase(cj). Then the string cannot be a palindrome, so we immediately return false.

3) If the characters match successfully, both pointers move toward the center of the string.

4) If the traversal completes without finding any mismatch, the string is a valid palindrome.

This solution is highly efficient because the string is processed only once.
public class A_TwoPointers {
    public boolean isPalindrome(String s) {
        int i = 0, j = s.length() - 1;

        while (i < j) {
            char ci = s.charAt(i);
            char cj = s.charAt(j);

            if (!Character.isLetterOrDigit(ci)) {
                i++;
            } else if (!Character.isLetterOrDigit(cj)) {
                j--;
            } else {
                // Compare lowercase versions
                if (Character.toLowerCase(ci) != Character.toLowerCase(cj)) {
                    return false;
                }
                i++;
                j--;
            }
        }
        return true;
    }
}

class Solution:

    def isPalindrome(self, s):

        i = 0
        j = len(s) - 1

        while i < j:

            while i < j and not s[i].isalnum():
                i += 1

            while i < j and not s[j].isalnum():
                j -= 1

            if s[i].lower() != s[j].lower():
                return False

            i += 1
            j -= 1

        return True
Time Complexity
O(n)
Space Complexity
O(1)

Conclusion

The Valid Palindrome problem is a classic string problem that teaches efficient character processing and the practical use of the two-pointer technique.

The problem demonstrates how unnecessary characters can be skipped while maintaining efficient traversal from both directions.

Mastering this problem helps build a strong understanding of string manipulation, character validation, and pointer-based traversal, which are frequently used in coding interviews and real-world applications.

💬 Comments