Valid Palindrome - Leetcode Solution

Problem Link

💡 Step-by-Step Thought Process

Understand the problem: Determine if a string is a palindrome, ignoring non-alphanumeric characters and case differences.
Get the length n of the input string s.
Initialize two pointers: L to 0 (start) and R to n-1 (end).
While L is less than R:
- If the character at s[L] is not alphanumeric, increment L and continue.
- If the character at s[R] is not alphanumeric, decrement R and continue.
- If the lowercase characters at s[L] and s[R] are not equal, return False.
Increment L and decrement R to check the next pair.
Return True if all checked characters match, indicating a palindrome.

Code Solution

class Solution:
    def isPalindrome(self, s: str) -> bool:
        n = len(s)
        L = 0
        R = n - 1

        while L < R:
            if not s[L].isalnum():
                L += 1
                continue

            if not s[R].isalnum():
                R -= 1
                continue

            if s[L].lower() != s[R].lower():
                return False

            L += 1
            R -= 1

        return True

# Time Complexity: O(n)
# Space Complexity: O(1)

#include <cctype>
#include <string>
using namespace std;

class Solution {
public:
    bool isPalindrome(string s) {
        int L = 0, R = s.size() - 1;

        while (L < R) {
            while (L < R && !isalnum(s[L])) {
                L++;
            }
            while (L < R && !isalnum(s[R])) {
                R--;
            }
            if (L < R && tolower(s[L]) != tolower(s[R])) {
                return false;
            }
            L++;
            R--;
        }
        return true;
    }
};

public class Solution {
    public boolean isPalindrome(String s) {
        int L = 0, R = s.length() - 1;

        while (L < R) {
            while (L < R && !Character.isLetterOrDigit(s.charAt(L))) {
                L++;
            }
            while (L < R && !Character.isLetterOrDigit(s.charAt(R))) {
                R--;
            }
            if (L < R && Character.toLowerCase(s.charAt(L)) != Character.toLowerCase(s.charAt(R))) {
                return false;
            }
            L++;
            R--;
        }
        return true;
    }
}

var isPalindrome = function(s) {
    let L = 0, R = s.length - 1;

    while (L < R) {
        while (L < R && !/[a-zA-Z0-9]/.test(s[L])) {
            L++;
        }
        while (L < R && !/[a-zA-Z0-9]/.test(s[R])) {
            R--;
        }
        if (L < R && s[L].toLowerCase() !== s[R].toLowerCase()) {
            return false;
        }
        L++;
        R--;
    }
    return true;
};

Detailed Explanation

Understanding the Problem

The "Valid Palindrome" problem asks us to determine whether a given string is a palindrome. A palindrome is a sequence that reads the same backward as forward. However, this variant of the problem ignores all non-alphanumeric characters and is case-insensitive. For example, "A man, a plan, a canal: Panama" is considered a valid palindrome.

Two-Pointer Technique

To solve this efficiently without using additional space to store a cleaned version of the string, we apply the two-pointer approach. We use two indices, one starting from the beginning of the string (L) and the other from the end (R), moving inward.

At each step, we skip any character that is not alphanumeric by advancing the pointers. If both characters are alphanumeric, we compare their lowercase versions. If at any point the characters differ, the string is not a palindrome, and we return false.

Step-by-Step Strategy

Initialize L = 0 and R = s.length - 1.
While L < R:
- If s[L] is not alphanumeric, increment L.
- If s[R] is not alphanumeric, decrement R.
- Compare lowercase(s[L]) and lowercase(s[R]). If they differ, return false.
- If they match, increment L and decrement R.
If the loop completes without mismatches, return true.

Why This Works

This method is efficient because it avoids the overhead of creating a new filtered string. By using the two-pointer approach, we ensure that we check character pairs directly within the original string. Lowercasing both characters standardizes comparison and skipping non-alphanumeric characters ensures compliance with the problem’s constraints.

Time and Space Complexity

The solution runs in O(n) time, where n is the length of the input string, since each character is visited at most once. The space complexity is O(1), as we only use a constant number of pointers and comparisons, making this approach optimal for large strings.

Get Personalized Support at AlgoMap Bootcamp 💡