Valid Palindrome

Given a string, return true if it is a palindrome after lowercasing and removing all non-alphanumeric characters. Otherwise return false.

A new filtered string works but costs extra memory. A two-pointer scan can do it in-place.

Function signature

func IsPalindrome(s string) bool

Inputs / outputs

• s: input string (ASCII letters/digits and punctuation).
• Return: true if the cleaned string is a palindrome.

Example

s = "A man, a plan, a canal: Panama"
Output: true

Cleaned: "amanaplanacanalpanama"

Constraints

• 0 <= len(s) <= 200_000

Core idea (near-solution)

Use two pointers l and r from both ends:

• Move l right until it hits an alphanumeric character.
• Move r left until it hits an alphanumeric character.
• Compare lowercased characters; if they differ, return false.

Invariant: all characters outside [l, r] have already been validated.

Algorithm (step-by-step)

1. Set l = 0, r = len(s)-1.
2. While l < r:
   • Advance l until s[l] is alphanumeric or l >= r.
   • Decrease r until s[r] is alphanumeric or l >= r.
   • Compare lowercased s[l] and s[r]; if different, return false.
   • Move l++, r--.
3. Return true.

Correctness sketch

• Invariant: all characters outside [l, r] have already been validated.
• Each step moves at least one pointer, shrinking the remaining search space.
• The invariant ensures elements outside the active window are already handled correctly.
• When pointers meet or cross, all candidates have been considered.

Trace (hand walkthrough)

Example input:
s = "A man, a plan, a canal: Panama"
Output: true

Cleaned: "amanaplanacanalpanama"

Walk:
- cleaned = "amanaplanacanalpanama"
- l=0,r=20: a==a -> move inward
- l=1,r=19: m==m -> move inward
- ... all pairs match -> true

Pitfalls to avoid

• Forgetting to skip non-alphanumeric characters on both ends.
• Comparing without lowercasing.
• Off-by-one when the string is empty.

Complexity

• Time: O(n)
• Extra space: O(1)

Implementation notes (Go)

• This statement assumes ASCII letters/digits.
• Implement small helpers isAlphaNum and toLower for bytes.