Valid Palindrome

Difficulty: Easy

Problem

Given a string s, return true if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Example

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Brute-force approach

Create a cleaned string (alphanumeric only, lowercase), reverse it, and compare with original cleaned string.

Steps

  1. Keep only letters and digits, convert to lowercase
  2. Create reversed string of the cleaned string
  3. Compare: if equal → palindrome, else → not a palindrome

Time complexity: O(n) · Space complexity: O(n)

Trade-offs

  • Creates extra strings
  • Uses O(n) extra space
  • Can we avoid copying?

Optimal approach

Key insight: A palindrome reads same forwards and backwards. Compare from both ends simultaneously!

Use two pointers from both ends, skip non-alphanumeric, compare in-place.

Steps

  1. Left pointer at start, right at end
  2. Skip non-alphanumeric characters
  3. Compare characters (case-insensitive)
  4. Move pointers inward

Time complexity: O(n) · Space complexity: O(1)