# 125. Valid Palindrome

LeetCode Problems

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

## Table of Content

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).