DEV Community

Cover image for LeetCode Challenge: 125. Valid Palindrome - JavaScript Solution πŸš€
Rahul Kumar Barnwal
Rahul Kumar Barnwal

Posted on

2 1 1 1 1

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.
Enter fullscreen mode Exit fullscreen mode

Example 2

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

Example 3

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

πŸ† 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);
}

Enter fullscreen mode Exit fullscreen mode

πŸ” 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"

Valid Palindrome
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('');
};
Enter fullscreen mode Exit fullscreen mode

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



Like and Share

Sentry blog image

How I fixed 20 seconds of lag for every user in just 20 minutes.

Our AI agent was running 10-20 seconds slower than it should, impacting both our own developers and our early adopters. See how I used Sentry Profiling to fix it in record time.

Read more

Top comments (1)

Collapse
 
rahulgithubweb profile image
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!

Postmark Image

Speedy emails, satisfied customers

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up