Problem Description

You need to determine if a given string is a valid palindrome when considering only alphanumeric characters and ignoring cases.

A palindrome reads the same forward and backward. For this problem, you must:

1. Convert all uppercase letters to lowercase
2. Remove all non-alphanumeric characters (keep only letters and numbers)
3. Check if the resulting string reads the same from left to right as it does from right to left

Given a string s, return true if it forms a valid palindrome under these rules, or false otherwise.

For example:

• "A man, a plan, a canal: Panama" becomes "amanaplanacanalpanama" after processing, which is a palindrome, so return true
• "race a car" becomes "raceacar" after processing, which is not a palindrome, so return false

The solution uses two pointers starting from opposite ends of the string. The pointers move toward each other, skipping non-alphanumeric characters and comparing the lowercase versions of valid characters. If all valid character pairs match, the string is a palindrome.

Intuition

The key insight is that we don't need to create a new cleaned string to check if it's a palindrome. Instead, we can check the palindrome property while skipping invalid characters on the fly.

Think about how you would manually check if a phrase is a palindrome:

1. You'd look at the first and last valid characters
2. Compare them (ignoring case)
3. Move inward to the next pair of valid characters
4. Repeat until you've checked all pairs

This naturally leads to a two-pointer approach. We place one pointer i at the beginning and another pointer j at the end of the string.

As we move the pointers toward each other:

• When i points to a non-alphanumeric character, we skip it by moving i forward
• When j points to a non-alphanumeric character, we skip it by moving j backward
• When both point to valid characters, we compare their lowercase versions
• If they match, we continue by moving both pointers inward
• If they don't match, we know it's not a palindrome

This approach is efficient because:

• We only traverse the string once (O(n) time)
• We don't need extra space to store a cleaned version of the string (O(1) space)
• We can return early as soon as we find a mismatch

The beauty of this solution is that it handles all the requirements (case insensitivity and non-alphanumeric characters) in a single pass without any preprocessing.

Solution Approach

The implementation uses the two-pointer technique to efficiently check if the string is a palindrome without creating a cleaned copy of the string.

Algorithm Steps:

1. Initialize two pointers: Set i = 0 pointing to the start of the string and j = len(s) - 1 pointing to the end.

2. Main loop: Continue while i < j:

   a. Skip non-alphanumeric from left: If s[i] is not alphanumeric (checked using s[i].isalnum()), increment i by 1 and continue to the next iteration.

   b. Skip non-alphanumeric from right: If s[j] is not alphanumeric, decrement j by 1 and continue to the next iteration.

   c. Compare valid characters: When both s[i] and s[j] are alphanumeric:

   • Convert both to lowercase using s[i].lower() and s[j].lower()
   • If they're not equal, return False immediately (not a palindrome)
   • If they match, move both pointers inward: i = i + 1 and j = j - 1

3. Return result: If the loop completes without finding mismatches, return True.

Key Implementation Details:

• The isalnum() method checks if a character is alphanumeric (letter or digit)
• The lower() method handles case-insensitive comparison
• The early return on mismatch (return False) optimizes performance for non-palindromes
• The pointer movement logic ensures we only compare valid characters

Time and Space Complexity:

• Time Complexity: O(n) where n is the length of the string. Each character is visited at most once.
• Space Complexity: O(1) as we only use two pointer variables regardless of input size.

This approach elegantly handles all edge cases including empty strings, strings with only non-alphanumeric characters, and strings with mixed cases and punctuation.

Example Walkthrough

Let's walk through the solution with the string "A man, a plan, a canal: Panama".

Initial Setup:

• String: "A man, a plan, a canal: Panama"
• i = 0 (pointing to 'A')
• j = 30 (pointing to 'a' at the end)

Step-by-step execution:

Iteration 1:

• s[0] = 'A' is alphanumeric ✓
• s[30] = 'a' is alphanumeric ✓
• Compare: 'A'.lower() = 'a' vs 'a'.lower() = 'a' → Match!
• Move pointers: i = 1, j = 29

Iteration 2:

• s[1] = ' ' is NOT alphanumeric
• Skip: i = 2, continue

Iteration 3:

• s[2] = 'm' is alphanumeric ✓
• s[29] = 'm' is alphanumeric ✓
• Compare: 'm'.lower() = 'm' vs 'm'.lower() = 'm' → Match!
• Move pointers: i = 3, j = 28

Iteration 4:

• s[3] = 'a' is alphanumeric ✓
• s[28] = 'a' is alphanumeric ✓
• Compare: 'a'.lower() = 'a' vs 'a'.lower() = 'a' → Match!
• Move pointers: i = 4, j = 27

Iteration 5:

• s[4] = 'n' is alphanumeric ✓
• s[27] = 'n' is alphanumeric ✓
• Compare: 'n'.lower() = 'n' vs 'n'.lower() = 'n' → Match!
• Move pointers: i = 5, j = 26

Iteration 6:

• s[5] = ',' is NOT alphanumeric
• Skip: i = 6, continue

Iteration 7:

• s[6] = ' ' is NOT alphanumeric
• Skip: i = 7, continue

Iteration 8:

• s[7] = 'a' is alphanumeric ✓
• s[26] = 'a' is alphanumeric ✓
• Compare: 'a'.lower() = 'a' vs 'a'.lower() = 'a' → Match!
• Move pointers: i = 8, j = 25

This pattern continues, with the algorithm:

• Skipping spaces, commas, and colons
• Comparing valid alphanumeric characters
• Moving both pointers inward when matches are found

Eventually, the pointers meet in the middle (when i >= j), and since all comparisons matched, the function returns True.

Key observations from this walkthrough:

• We never created a cleaned string - we handled everything on the fly
• Non-alphanumeric characters were seamlessly skipped
• Case differences were handled during comparison
• The algorithm efficiently validated the palindrome in a single pass

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string s. In the worst case, the algorithm needs to traverse the entire string once using the two-pointer approach. Each character is visited at most once by either pointer i or j. Even though there are conditional checks for alphanumeric characters, the total number of iterations is still bounded by n since each iteration either advances i, decrements j, or both.

The space complexity is O(1). The algorithm only uses a constant amount of extra space for the two pointers i and j, regardless of the input size. The operations isalnum() and lower() are performed in-place without creating new data structures, and no additional arrays, strings, or other data structures that scale with input size are created.

Common Pitfalls

1. Incorrect Pointer Movement Logic

One of the most common mistakes is moving both pointers simultaneously when encountering non-alphanumeric characters, or forgetting to use continue statements after moving a single pointer.

Incorrect Implementation:

while left_index < right_index:
    if not s[left_index].isalnum():
        left_index += 1
    if not s[right_index].isalnum():  # Bug: This should be 'elif'
        right_index -= 1
    # This comparison might execute even when we just skipped characters!
    elif s[left_index].lower() != s[right_index].lower():
        return False
    else:
        left_index += 1
        right_index -= 1

The Problem: When the left character is non-alphanumeric, we increment left_index, but then we still check the right character and potentially compare characters that we haven't properly validated yet.

Solution: Use elif statements or continue to ensure only one action happens per iteration:

while left_index < right_index:
    if not s[left_index].isalnum():
        left_index += 1
        continue  # Skip to next iteration
    if not s[right_index].isalnum():
        right_index -= 1
        continue  # Skip to next iteration
    if s[left_index].lower() != s[right_index].lower():
        return False
    left_index += 1
    right_index -= 1

2. Infinite Loop When All Characters Are Non-Alphanumeric

Problematic Pattern:

while left_index < right_index:
    while not s[left_index].isalnum():  # Danger: No bounds check!
        left_index += 1
    while not s[right_index].isalnum():  # Danger: No bounds check!
        right_index -= 1
    # ... comparison logic

The Problem: If the string contains only non-alphanumeric characters (like ".,!@#"), the inner while loops will go out of bounds causing an IndexError.

Solution: Always include boundary checks in inner loops:

while left_index < right_index:
    while left_index < right_index and not s[left_index].isalnum():
        left_index += 1
    while left_index < right_index and not s[right_index].isalnum():
        right_index -= 1
    if left_index < right_index:  # Check again before comparing
        if s[left_index].lower() != s[right_index].lower():
            return False
        left_index += 1
        right_index -= 1

3. Using <= Instead of < in the While Condition

Incorrect:

while left_index <= right_index:  # Bug: Should be '<'

The Problem: When left_index == right_index, we're pointing at the same character in the middle of an odd-length string. Comparing it with itself is unnecessary and could cause issues if the logic isn't structured properly.

Solution: Use < to stop when pointers meet or cross:

while left_index < right_index:

This correctly handles both even and odd-length strings without unnecessary comparisons.