Domain 1EasyCORE

Valid Palindrome

The problem asks us to determine if a given string `s` is a palindrome, considering only alphanumeric characters and ignoring cases. A palindrome is a sequence that reads the same backward as forward.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Two Pointers#String

125. Valid Palindrome

Model: qwen2.5-coder:14b
Topics: Two Pointers,String
FAANG asked: 1
Acceptance rate: 38.5%


Problem Breakdown

The problem asks us to determine if a given string s is a palindrome, considering only alphanumeric characters and ignoring cases. A palindrome is a sequence that reads the same backward as forward.

Inputs:

  • A single string s.

Outputs:

  • A boolean value indicating whether the string is a palindrome or not.

Implicit Constraints/Edge Cases:

  • The string may contain non-alphanumeric characters (e.g., spaces, punctuation) which should be ignored.
  • The comparison should be case-insensitive.
  • An empty string or a single character string should return true as they are trivially palindromes.
  • Strings with only non-alphanumeric characters should also return true.

Intuition

A brute-force approach would involve removing all non-alphanumeric characters, converting the string to lowercase, and then checking if the resulting string is equal to its reverse. This approach has a time complexity of O(n) for cleaning the string and another O(n) for reversing it, making it O(2n) or simply O(n). However, this can be optimized.

The key insight is that we don’t need to create a new cleaned string. Instead, we can use two pointers: one starting at the beginning of the string and the other at the end. We move these pointers towards each other, skipping non-alphanumeric characters and comparing the alphanumeric characters in a case-insensitive manner. This approach reduces the space complexity to O(1) since we are not using any additional data structures.

Approach

  1. Initialize two pointers: left starting at the beginning of the string and right starting at the end.
  2. Move the left pointer to the right until it points to an alphanumeric character or crosses the right pointer.
  3. Move the right pointer to the left until it points to an alphanumeric character or crosses the left pointer.
  4. Compare the characters at the left and right pointers in a case-insensitive manner.
  5. If they are not equal, return false.
  6. If they are equal, move both pointers towards each other and repeat steps 2-5.
  7. If the loop completes without finding any mismatched characters, return true.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the string. Each character is checked at most once.
  • Space Complexity: O(1). No additional space is used other than a few variables for pointers and temporary storage.

Solution

class Solution:
    def isPalindrome(self, s: str) -> bool:
        left, right = 0, len(s) - 1
        
        while left < right:
            # Move the left pointer to the next alphanumeric character
            while left < right and not s[left].isalnum():
                left += 1
            # Move the right pointer to the previous alphanumeric character
            while left < right and not s[right].isalnum():
                right -= 1
            
            # Compare characters in a case-insensitive manner
            if s[left].lower() != s[right].lower():
                return False
            
            # Move both pointers towards each other
            left += 1
            right -= 1
        
        return True

Edge Cases Handled

  • Empty String: The loop condition left < right ensures that the function returns true immediately.
  • Single Character String: Similar to the empty string case, the loop will not execute and true is returned.
  • Strings with Only Non-Alphanumeric Characters: Both pointers will eventually cross each other without finding any mismatched characters, resulting in a return value of true.
  • Mixed Case Strings: The comparison is done in lowercase, ensuring case insensitivity.