Valid Palindrome

Problem Summary

• Determine whether a given string is a valid palindrome or not

What is Being Asked?

• Return True or False

Key Observations

(Patterns, constraints, or hints in the problem statement.)

• Input contains non-alpha-numeric characters as well
• We need to only check for alpha-numeric characters
• We need to also ensure we compare lower characters

Main Concepts Used

(Mark the CS concepts or algorithms used.)

• Two Pointers#1. Opposite Direction Pointers (Start–End)
• Strings

Time & Space Complexity

• Time: $O(n)$ → Reason: Iterating through each element once
• Space: $O(1)$ → Reason: Not storing anything except two pointers

Code

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

        while l < r:
            while l < r and not s[l].isalnum():
                l += 1
            
            while l < r and not s[r].isalnum():
                r -= 1

            if s[l].lower() != s[r].lower():
                return False
            l += 1
            r -= 1
        return True

Common Mistakes / Things I Got Stuck On

• Need to make sure to use the correct function isalnum()
• Decrementing pointers
• Expression for while loop < less than because the middle will always be a valid palindrome