Solution: Valid Palindrome

Grokking the Coding Interview: Patterns for Coding Questions

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Valid Palindrome

Table of Contents

Contents are not accessible

Problem Statement

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: sentence = "A man, a plan, a canal, Panama!"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:

Input: sentence = "Was it a car or a cat I saw?"
Output: true
Explanation: Explanation: "wasitacaroracatisaw" is a palindrome.

Example 3:

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

Constraints:

1 <= s.length <= 2 * 10<sup>5</sup>
s consists only of printable ASCII characters.

Solution

This problem aims to check if a given string is a palindrome. A palindrome is a word, phrase, number, or other sequences of characters that read the same forward and backward, ignoring spaces, punctuation, and capitalization. Our algorithm can leverage the two-pointer technique where one pointer starts at the beginning of the string, and the other one starts at the end. The two pointers move towards each other, checking if the characters they point to are the same.

Walkthrough of the algorithm

Let's take a detailed walkthrough of the code:

The isPalindrome function starts by setting two pointers: 'i' at the start of the string and 'j' at the end.
Then it enters a while loop which continues until the two pointers cross each other. Inside this loop:
- The first inner while loop moves 'i' forward, skipping any characters that are not letters or digits, until it points to a valid character or it crosses 'j'.
- The second inner while loop moves 'j' backward, skipping any characters that are not letters or digits, until it points to a valid character or it crosses 'i'.
After finding valid characters at 'i' and 'j', it converts these characters to lowercase and checks if they're the same.
- If they're not the same, the function immediately returns false since the string can't be a palindrome if these characters are different.
- If they are the same, 'i' is incremented and 'j' is decremented, and the loop continues to the next pair of characters.
If the while loop completes without finding any unequal pairs of characters, the function returns true, indicating that the string is a palindrome.

Code

Here is the code for this algorithm:

Python3

. . . .

Complexity Analysis

Time Complexity

Two-pointer traversal: The algorithm uses two pointers, i starting from the left and j from the right, and moves them inward toward each other. The loop runs until the two pointers meet or cross over, meaning we traverse the string once. This results in a time complexity of $O(N)$ , where N is the length of the input string.
Nested loops (for skipping non-alphanumeric characters):
- Within the main loop, we use two while loops to skip non-alphanumeric characters. Each of these inner loops also runs at most N times in total, as each character is only skipped once. Even though the loops are nested, their total number of iterations is still proportional to the size of the string.
Character comparisons: Each valid alphanumeric character is compared after converting to lowercase, which is a constant time operation, $O(1)$ .

Overall time complexity: $O(N)$ .

Space Complexity

Constant space: The algorithm only uses a few extra variables (i, j) and performs character operations in place. No additional data structures are used that scale with the input size.

Overall space complexity: $O(1)$ .

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible