Valid Palindrome

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backwards. Alphanumeric characters include letters and numbers.

Are you tired of reading palindrome from both ends, only to find out that it’s not a valid one? Don’t worry, you’re not alone. Today we’re going to explore different approaches to tackle this challenge — from brute force to more optimized solutions. So buckle up, grab your favourite beverage, and let’s dive into the wild world of palindrome detection!

Problem Statement:

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

---

Approach 1: Brute Force

The simplest approach is to compare the string with its reverse. To reverse the string, We can either use a built-in function or write a loop to traverse the string from end to start and concatenate the characters.

1. Firstly, remove all the non-alphanumeric characters (replace and regex) from the input string and convert it to lowercase (built-in method).

2. Then, compare the string with its reverse using a for loop that iterates over half of the input string’s length, checking if each character matches its corresponding character from the end of the string.

3. If a mismatch is found, the function returns false, indicating that the string is not a valid palindrome. Otherwise, it returns true.

// ES6 Arrow Function
const validPalindrome = s => {

    // Remove non-alphanumeric char and convert to lower cases 
    s = s.replace(/[^0-9a-zA-Z]/g, '').toLowerCase();

    // compare the string with its reverse
    for(let i = 0; i < s.length / 2; i++) {
        if(s[i] !== s[s.length - 1 - i]) {
            return false;
        }
    }

    return true;
}

Time Complexity: O(N)

Space Complexity: O(N), This is because the function creates a new string that contains only alphanumeric characters and is the same length as the original string.

---

Approach 1.1: Without Regular Expression

So the idea is to iterate over each character of the input string and for each character, convert it to lowercase and check if it’s alphanumeric. If the character is alphanumeric, then add it to a new string. Otherwise, move to the next character.

// ES6 Arrow Function

const isPalindrome = s => {
    // Remove non-alphanumeric characters and convert to lowercase
    let cleanString = "";
    for (let i = 0; i < s.length; i++) {
      const char = s[i].toLowerCase();
      if ((char >= "a" && char <= "z") || (char >= "0" && char <= "9")) {
        cleanString += char;
      }
    }

    // Compare the string with its reverse
    for (let i = 0; i < cleanString.length / 2; i++) {
      if (cleanString[i] !== cleanString[cleanString.length - 1 - i]) {
        return false;
      }
    }

    return true;
}

Time Complexity: O(N)

Space Complexity: O(N)

---

Approach 2: Two Pointers

A more efficient approach is to use two pointers, one starting from the beginning and one from the end, and compare the characters as you move towards the middle.

1. We create two pointers i and j. One initialized at the beginning and one at the end of the input string.

2. We also create a helper function isAlphaNumeric(). This will help us determine whether the given character is alphanumeric or not.

3. When the loop begins, we check at each iteration, if the characters at positions i and j are alphanumeric using the isAlphanumeric() helper function.

4. If one of them is not alphanumeric, it increments or decrements the corresponding pointer until it finds an alphanumeric character.

5. Once it has found two alphanumeric characters at positions i and j, it compares them.

6. If they are not equal, the function returns false, indicating that the string is not a valid palindrome.

7. Otherwise, it increments i and decrements j and continues with the next iteration of the loop.

// ES6 Arrow Function

// Helper Function
const isAlphanumeric = char => {
    const code = char.charCodeAt(0);
    return (code >= 97 && code <= 122) || (code >= 48 && code <= 57);
}

// Palindrome check
const isPalindrome = s => {
    s = s.toLowerCase();

    let i = 0, j = s.length - 1;

    // compare characters from left and right pointers
    while (i < j) {
        while (i < j && !isAlphanumeric(s[i])) {
          i++;
        }

        while (i < j && !isAlphanumeric(s[j])) {
          j--;
        }

        if (s[i] !== s[j]) {
          return false;
        }

        i++;
        j--;
    }

    return true;
}

Time Complexity: O(N)

Space Complexity: O(1)

---

And there you have it guys! We’ve explored different approaches, optimized our solutions, and hopefully had some fun along the way. I hope this article has provided you with valuable insights and helped you better understand the different approaches to solving this problem. Happy coding!

Problem - Leetcode 125