Vaild Palindrome

Easy

📘 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

Example 1:

Input: s = “A man, a plan, a canal: Panama”

Output: true

Explanation: “amanaplanacanalpanama” is a palindrome.

---

🛠️ Solution

The idea is to use two -pointer, one starting from the beginning(left pointer) of the string and other starting from the end (right pointer). If string is a palindrome, at all time, character pointed by the left pointer and right pointer should be same. We keep on increasing the left pointer and decreasing the right pointer until we left and right pointer meet / overlap at which stage, we can terminate our iteration. At any point, if the character is non-alphanumeric, we skip that character.

def is_palindrome(s: str) -> bool:
    left, right = 0, len(s) - 1

    while left < right:
        # Skip non-alphanumeric characters from the left
        while left < right and not s[left].isalnum():
            left += 1
        # Skip non-alphanumeric characters from the right
        while left < right and not s[right].isalnum():
            right -= 1

        # Compare characters in lower case
        if s[left].lower() != s[right].lower():
            return False

        left += 1
        right -= 1

    return True

🕒 Time Complexity: \(O(n)\)

📦 Space Complexity: \(O(1)\)