LeetCode 125 - Valid Palindrome

This problem asks whether a string is a palindrome after keeping only alphanumeric characters and ignoring case. I first thought about building a filtered copy, but the same check can be done cleanly by narrowing in from both ends of the original string.

---

Problem link and explanation

• Problem link: 125. Valid Palindrome
• Summary: Given a string s, return true if it is a palindrome after considering only alphanumeric characters and ignoring case, otherwise return false.

For example, "A man, a plan, a canal: Panama" becomes a palindrome once punctuation and spaces are ignored. "race a car" does not.

The key point is that the comparison rules are not the same as plain string comparison. Non-alphanumeric characters should be skipped, and uppercase and lowercase letters should be treated as the same character.

---

Approach

One natural approach is to filter the string first and then compare the result with two pointers.

new_str = ""
for ch in s:
    if ch.isalnum():
        new_str += ch.lower()

That version is easy to follow, but it creates a new string, so it uses extra space. In terms of space complexity, the direct two-pointer version is better.

The final solution keeps the original string and moves two pointers from both ends toward the center. If the left character is not alphanumeric, I move left forward. If the right character is not alphanumeric, I move right backward. Once both sides point to valid characters, I compare them in lowercase. If they differ, I return false. Otherwise, I move both pointers inward and continue.

This avoids building a filtered copy and keeps the space usage constant.

---

Troubleshooting

The first thing to get right is the skipping rule. Both pointers have to apply the same isalnum() check, or the comparison positions drift out of sync.

Case normalization is the second part. "A" and "a" must compare as equal, so I convert both sides to lowercase right before comparing.

One more edge case is a string that contains only punctuation or spaces. In that case, the pointers keep skipping until they meet, and the answer is still true. An empty string follows the same rule.

---

Complexity analysis

• Time complexity: O(n)

  • Each pointer moves from the outside to the center at most once.
  • Each character is examined a constant number of times.

• Space complexity: O(1)

  • The solution uses only pointer variables and a few temporary checks.

The filtered-string version is also valid, but it uses O(n) extra space because it stores the normalized copy.

---

Implementation code

The final code uses two pointers directly on the original string.

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

        while left < right:
            if not s[left].isalnum():
                left += 1
                continue

            if not s[right].isalnum():
                right -= 1
                continue

            if s[left].lower() != s[right].lower():
                return False

            left += 1
            right -= 1

        return True

The solution stays simple because the comparison rule is handled directly in the pointer loop. There is no need to materialize a second string unless readability matters more than space.

---

Summary and reflection

This is an Easy problem, but it can still get annoying if you overcomplicate it. The important part is to simplify the rule as much as possible.

Building a filtered string is a reasonable first pass, but keeping the original string and moving the pointers directly is cleaner in space. Once the rule is clear, the rest is just a standard two-pointer scan.