Skip to main content

🟩 Valid Palindrome (#125)

🔗 Problem Link​

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

💡 Examples​

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: Empty string after removing non-alphanumeric is "", which is a palindrome.

🔑 Key Insights & Approach​

Core Observation: Use two pointers from opposite ends, skip non-alphanumeric characters, compare lowercase versions.

Why Two Pointers?

  • O(n) time, single pass
  • O(1) space - no string creation needed
  • Clean and efficient

Approaches:

  1. Filter string then reverse: O(n) time, O(n) space
  2. Two pointers with skip logic: O(n) time, O(1) space - optimal

Pattern: "Two Pointers - Opposite Ends" pattern for palindrome verification.

🐍 Solution: Python​

Approach: Two Pointers with Skip Logic​

Time Complexity: O(n) | Space Complexity: O(1)

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

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

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

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

            left += 1
            right -= 1

        return True

Approach 2: Filter Then Compare​

Time Complexity: O(n) | Space Complexity: O(n)

class Solution:
    def isPalindrome(self, s: str) -> bool:
        # Filter and lowercase
        filtered = ''.join(c.lower() for c in s if c.isalnum())

        # Compare with reverse
        return filtered == filtered[::-1]

🔵 Solution: Golang​

Approach: Two Pointers with Skip Logic​

Time Complexity: O(n) | Space Complexity: O(1)

import "unicode"

func isPalindrome(s string) bool {
    left, right := 0, len(s)-1

    for left < right {
        // Skip non-alphanumeric from left
        for left < right && !isAlphaNum(rune(s[left])) {
            left++
        }

        // Skip non-alphanumeric from right
        for left < right && !isAlphaNum(rune(s[right])) {
            right--
        }

        // Compare lowercase characters
        if unicode.ToLower(rune(s[left])) != unicode.ToLower(rune(s[right])) {
            return false
        }

        left++
        right--
    }

    return true
}

func isAlphaNum(c rune) bool {
    return unicode.IsLetter(c) || unicode.IsDigit(c)
}

📚 References​