Valid Palindrome

Question link: https://leetcode.com/problems/valid-palindrome/description/

Problem: 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 backward. Alphanumeric characters include letters and numbers.

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

Example 1:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:

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

Example 3:

Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.

Constraints:

• 1 <= s.length <= 2 * 105
• s consists only of printable ASCII characters.

Walkthrough

A palindrome is essentially a phrase that reads the same backwards and forwards. This question asks us to clean up the phrase before we do our checks. Let’s walkthrough the logic in plain english

Plain English logic

• First we’d need to clean up our phrase, that is, convert all uppercase to lowercase and remove all non-alphanumeric character
• Then we can loop through the processed phrase. Since we palindromes are the same forwards and back, we can have 2 pointers that point to the first and last element and work up/down from there
• If the first and last element does not match then return false. else add 1 to the first pointer and minus 1 from the last point(cave into the middle element).
• If the left pointer is greater than the right pointer then we should stop and return true.

Ok let’s convert this into code

Code solution

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function(s) {
    let processedS = s.toLowerCase().replace(/[^a-zA-Z0-9]/g, '')

    let left = 0
    let right = processedS.length - 1

    while (left <= right) {
        if (processedS[left] !== processedS[right]) {
            return false
        }
        left+=1
        right-=1
    }
    return true
};

Analysis

Time complexity

The time complexity of this is O(n) because we need to loop through the input string twice, i.e. to form a string with (1) only lowercase and (2) alphanumeric characters. The while loop is at most only O(n/2) => O(n) which brings our final time complexity to O(n).

Space complexity

The space complexity is O(n) as the size of processedS depends on the size of the input i.e. s.