125. Valid Palindrome

In this tutorial we will solve 125. Valid Palindrome from leetcode.

Table of Content

• Reference
• Problem Statement
• Approach
• Code
• Complexity

Reference: 125. Valid Palindrome

Problem statement

In this problem we are asked to return true if a given input string s is a palindrome.

There are conditions that we have to consider for this problem statement. We have to convert the string into lowercase. We also have to remove all non-alphanumeric characters.

Alphanumeric characters include letters and numbers. Therefore, we can consider any other characters as non-alphanumeric.

Example from leetcode.

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 * 10^5
s consists only of printable ASCII characters.

Approach

To solve this problem we will first remove all non-alphanumerical characters from the input string s. Then we will convert all the uppercase characters to lowercase characters. Now, we will use two pointers to check if the input string is a palindrome.

The first pointer i will start from the beginning of the input string. The second pointer j will start from the end of the input string. In each iteration we will check if the character at index i and j are equal. If they are equal then we will increase i by 1 and we will decrease j by 1. We continue this comparison as long as i < j. If at any point character at index i and j are not equal then we will say that the input string is not a palindrome.

Let's solve the input s = "A man, a plan, a canal: Panama".

s = "A man, a plan, a canal: Panama"
removing non-alphanumeric characters

s = "AmanaplanacanalPanama"

convert to lowercase

s = "amanaplanacanalpanama"
     ^                   ^
     i                   j

is i < j and s[i] === s[j] ? yes
  -> increment i
  -> decrement j


s = "amanaplanacanalpanama"
      ^                 ^
      i                 j

is i < j and s[i] === s[j] ? yes
  -> increment i
  -> decrement j


s = "amanaplanacanalpanama"
       ^               ^
       i               j

is i < j and s[i] === s[j] ? yes
  -> increment i
  -> decrement j


s = "amanaplanacanalpanama"
        ^             ^
        i             j

is i < j and s[i] === s[j] ? yes
  -> increment i
  -> decrement j


s = "amanaplanacanalpanama"
         ^           ^
         i           j

is i < j and s[i] === s[j] ? yes
  -> increment i
  -> decrement j


s = "amanaplanacanalpanama"
          ^         ^
          i         j

is i < j and s[i] === s[j] ? yes
  -> increment i
  -> decrement j


s = "amanaplanacanalpanama"
           ^       ^
           i       j

is i < j and s[i] === s[j] ? yes
  -> increment i
  -> decrement j


s = "amanaplanacanalpanama"
            ^     ^
            i     j

is i < j and s[i] === s[j] ? yes
  -> increment i
  -> decrement j


s = "amanaplanacanalpanama"
             ^   ^
             i   j

is i < j and s[i] === s[j] ? yes
  -> increment i
  -> decrement j


s = "amanaplanacanalpanama"
              ^ ^
              i j

is i < j and s[i] === s[j] ? yes
  -> increment i
  -> decrement j


s = "amanaplanacanalpanama"
               ^
               i
               j

is i < j and s[i] === s[j] ? no
  -> checking ends here

Code

JavaScript

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function(s) {
  const onlyLowerCaseAlnum = s.toLowerCase().replace(/[^a-z0-9]/g, '');
  let i = 0;
  let j = onlyLowerCaseAlnum.length - 1;
  while(i < j) {
    if (onlyLowerCaseAlnum[i] !== onlyLowerCaseAlnum[j]) {
      return false;
    }
    i++;
    j--;
  }
  return true;
};

Complexity

Time complexity: O(n)

Converting the input string to lowercase will take O(n) time. Removing non-alphanumeric characters will take O(n). The while loop will run for O(n) time. Therefore, the overall time complexity will be O(n).

Space complexity: O(n)

Space for only lowercase alphanumeric characters will be O(n). The two pointers will take O(1) space. The overall space complexity will be O(n).