LeetCode 125 - Valid Palindrome

Table of Contents

Problem

Determine if a given string s is a palindrome, considering only alphanumeric characters and ignoring cases. A palindrome is a word that reads the same backward as forward.

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.

Explanation/Approach

Using Two Pointers:

• Preprocess String: Convert all characters to lowercase and remove non-alphanumeric characters.
• Two Pointers: Initialize two pointers, one at the start and another at the end of the string.
• Compare Characters: Move the pointers towards the center, comparing characters at each step.
• Early Termination: If any mismatch is found, return false.
• Completion: If pointers cross without any mismatch, return true.

Solution: Two Pointers

class Solution:
    def isPalindrome(self, s: str) -> bool:
        left, right = 0, len(s) - 1

        while left < right:
            # Move left pointer to the next alphanumeric character
            while left < right and not s[left].isalnum():
                left += 1
            # Move right pointer to the previous alphanumeric character
            while right > left and not s[right].isalnum():
                right -= 1

            if s[left].lower() != s[right].lower():
                return False

            left += 1
            right -= 1

        return True

Time and Memory Complexity

• Time Complexity: O(n), where n is the length of the string s. The string is traversed at most once.
• Memory Complexity: O(1), as no additional space is required beyond the input string.

Visual Representation

Initial String:

"A man, a plan, a canal: Panama"

• We start with two pointers, one at the beginning (left) and one at the end (right) of the string.

Pointer Movement and Comparison:

• Step 1:
  • left = 0 (pointing to ‘A’), right = 24 (pointing to ‘a’).
  • Both are alphanumeric and lowercase comparison is a == a, which is true. Move both pointers.
• Step 2:
  • left = 1 (pointing to ’ ’), right = 23 (pointing to ‘m’).
  • left is not alphanumeric, so move left to the next alphanumeric character.
• Step 3:
  • After skipping non-alphanumeric characters, left = 2 (pointing to ‘m’), right = 23.
  • Now, the comparison is m == m, which is true. Move both pointers.
• Step 4 and so on:
  • Continue this process, moving left to the right and right to the left, skipping non-alphanumeric characters and comparing corresponding characters.
• Final Step:
  • When left and right pointers cross each other, all comparisons have been made.

4. Result:
   • If all corresponding characters matched, return true.
   • If any mismatch is found during the comparisons, return false.

In our example, all the comparisons will be true, and the pointers will eventually cross each other without finding any mismatch, confirming that the string is a palindrome after considering only the alphanumeric characters and ignoring the cases.

Here’s a step-by-step visual representation of the pointer movement:

"A man, a plan, a canal: Panama"
 ^                            ^
left                         right

"A  man, a plan, a canal: Panama"
   ^                          ^
  left                       right

"A  man, a plan, a canal: Panama"
    ^                         ^
   left                     right

...

"A man, a plan, a canal: Panama"
                ^  ^
            left   right

• The pointers move towards each other, skipping non-alphanumeric characters, and keep comparing the characters they point to.
• When they meet or cross, if no mismatches have been found, the string is a palindrome.