LeetCode Problems

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

Reference: 125. Valid Palindrome

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

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
```

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;
};
```

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

ADVERTISEMENT