LeetCode Challenge: 125. Valid Palindrome - JavaScript Solution 🚀

Top Interview 150

The Valid Palindrome problem is a common challenge that tests your ability to process strings and work with character validation. Let’s tackle LeetCode 125: Valid Palindrome step by step.

---

🚀 Problem Description

A phrase is a palindrome if, after:

• Converting all uppercase letters to lowercase.
• Removing all non-alphanumeric characters.

The phrase reads the same backward as forward.
Return true if the input string s is a palindrome; otherwise, return false.

---

💡 Examples

Example 1

Input: s = "A man, a plan, a canal: Panama"  
Output: true  
Explanation: After cleaning, "amanaplanacanalpanama" reads the same backward.

Example 2

Input: s = "race a car"  
Output: false  
Explanation: After cleaning, "raceacar" is not a palindrome.

Example 3

Input: s = " "  
Output: true  
Explanation: After cleaning, the string becomes empty and is considered a palindrome.

---

🏆 JavaScript Solution

We can solve this problem by using a two-pointer approach to check if the cleaned string is a palindrome.

Implementation

var isPalindrome = function(s) {
    let left = 0;
    let right = s.length - 1;

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

        if (s[left].toLowerCase() !== s[right].toLowerCase()) {
            return false;
        }

        left++;
        right--;
    }

    return true;
};

function isAlphanumeric(char) {
    return /^[a-zA-Z0-9]$/.test(char);
}

---

🔍 How It Works

1. Two Pointers:

   • Start with pointers at the beginning (left) and end (right) of the string.
   • Move the pointers toward each other.

2. Skip Non-Alphanumeric Characters:

   • Use a helper function isAlphanumeric() to determine valid characters.
   • Skip invalid characters by moving the pointers.

3. Compare Characters:

   • Convert both characters to lowercase using toLowerCase() before comparing.
   • If the characters don’t match, return false.

4. Check All Characters:

   • If the loop completes without mismatches, return true.

---

🔑 Complexity Analysis

• Time Complexity: O(n), where n is the length of the string.

  • Each character is processed once by the two pointers.

• Space Complexity: O(1), as no additional data structures are used.

---

📋 Dry Run

Input: "A man, a plan, a canal: Panama"

Output: true

---

Alternative Solution: Clean and Reverse
Another approach involves cleaning the string and checking if it matches its reverse.

var isPalindrome = function(s) {
    const cleaned = s.replace(/[^a-zA-Z0-9]/g, '').toLowerCase();
    return cleaned === cleaned.split('').reverse().join('');
};

---

Complexity:

• Time Complexity: O(n), for cleaning, reversing, and comparing the string.
• Space Complexity: O(n), for the cleaned string and reversed string.

---

✨ Pro Tips for Interviews

1. Handle Edge Cases:

   • Empty strings ("") → true.
   • Strings with only non-alphanumeric characters (e.g., "!!") → true.

2. Highlight Efficiency:

   • The two-pointer approach is space-efficient.
   • The clean-and-reverse method is simpler but uses more memory.

3. Explain Helper Functions:

   • Discuss why using a regex-based isAlphanumeric() is clear and effective.

---

📚 Learn More

Check out the detailed explanation and code walkthrough on my Dev.to post:
👉 Text Justification - JavaScript Solution

Which approach do you prefer? Let’s discuss! 🚀

JavaScript #LeetCode #CodingInterview #ProblemSolving

---

---

Comments

[Rahul Kumar Barnwal]

Follow Me on GitHub 🚀

If you found this solution helpful, check out more of my projects and solutions on my GitHub profile.

Don't forget to follow for more updates!