Valid Palindrome

Difficulty: Easy
Topics: Two Pointers, String
Link: https://leetcode.com/problems/valid-palindrome/

Problem Description

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

Example 1:


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

Example 2:


Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.

Example 3:


Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.

Constraints:

1 <= s.length <= 2 * 105
s consists only of printable ASCII characters.

Solution

1. Problem Deconstruction

Technical Restatement

Given a string s of printable ASCII characters (length 1 to 200,000), implement a function that:

Normalizes s by:
- Converting all alphabetic characters to lowercase
- Removing all non-alphanumeric characters (retain [a-z0-9])
Returns true if the normalized string is a palindrome (reads identically forwards/backwards), else false.

Beginner-Friendly Explanation

Imagine cleaning up a messy sentence:

Erase all spaces, punctuation, and symbols (e.g., ",", ":", " ")
Convert all letters to lowercase (e.g., "A" → "a")
Check if the cleaned string is a mirror image of itself (e.g., “radar” reversed is still “radar”).

Mathematical Formulation

Let:

$s$ = input string of length $n$
$f: \text{char} \rightarrow \text{char} \cup \{\emptyset\}$ be a filtering function: $f(c) = \begin{cases} \text{lowercase}(c) & \text{if } c \text{ is alphanumeric} \\ \emptyset & \text{otherwise} \end{cases}$
$t = [f(s_0), f(s_1), \dots, f(s_{n-1})] \text{ without } \emptyset$ (filtered sequence)
$t$ is a palindrome iff: $\forall i \in \left[0, \left\lfloor \frac{|t|}{2} \right\rfloor \right), t_i = t_{|t|-1-i}$

Constraint Analysis

1 <= s.length <= 2e5:
- Limitation: Rules out O( $n^2$ ) solutions (e.g., nested loops).
- Edge Case: Single-character strings are trivially palindromic.
Printable ASCII Characters:
- Limitation: Non-alphanumeric chars (e.g., !, @) must be skipped efficiently.
- Edge Case: Strings with only non-alphanumeric chars (e.g., "!@#") become empty → valid palindrome.
Alphanumeric Definition:
- Edge Case: Numbers included (e.g., "12321" is valid). Case sensitivity handled via lowercase conversion.

2. Intuition Scaffolding

Analogies

Real-World Metaphor:
- Magazine Cutout Ransom Note: Cut alphanumeric letters, convert to lowercase, arrange on a board. Hold the board up to a mirror—letters should match when viewed normally and in reflection.
Gaming Analogy:
- Portal Mirror Test: Shoot a “character cleaning ray” that removes non-alphanumeric chars and converts uppercase to lowercase. The ray reflects off a central mirror—if the pre-reflection and post-reflection sequences match, the level is solved.
Math Analogy:
- Symmetric Matrix Check: Treat the filtered string as a vector $\mathbf{t}$ . Construct a reflection matrix $\mathbf{R}$ where $R_{ij} = 1$ if $i + j = |\mathbf{t}|-1$ , else $0$ . Then $\mathbf{t}$ is palindromic iff $\mathbf{R} \mathbf{t} = \mathbf{t}$ .

Common Pitfalls

Case Sensitivity Neglect:
- Comparing 'A' and 'a' as unequal without lowercase conversion.
Ignoring Non-Alphanumeric Characters:
- Including spaces/punctuation in comparison (e.g., comparing "a," and ",a").
Midpoint Miscalculation:
- Forgetting that odd-length palindromes skip the center index.
Unoptimized Filtering:
- Building a new string with += in a loop (O( $n^2$ ) time).
Overcleaning:
- Removing alphanumeric chars incorrectly (e.g., deleting digits).

3. Approach Encyclopedia

Approach 1: Brute Force (Two-Pass)

Filter & Lowercase: Create a new string clean_s by iterating through s, appending only alphanumeric chars in lowercase.
Palindrome Check: Compare clean_s with its reverse.

Pseudocode:

def isPalindrome(s):
    clean_chars = []
    for char in s:
        if char.isalnum():
            clean_chars.append(char.lower())
    clean_s = ''.join(clean_chars)
    return clean_s == clean_s[::-1]

Complexity Proof:
- Time: O( $n$ ) for filtering + O( $n$ ) for reversal → O( $n$ ).
- Space: O( $n$ ) for clean_chars and clean_s.

Visualization:

s = "A man..."  
Filter: ['a','m','a','n','a','p','l','a','n','a','c','a','n','a','l','p','a','n','a','m','a']  
Reverse: ['a','m','a','n','a','p','l','a','n','a','c','a','n','a','l','p','a','n','a','m','a'] → Match!

Approach 2: Optimal (Two-Pointer, Single Pass)

In-Place Validation: Use left/right pointers starting at both ends. Skip non-alphanumeric chars and compare lowercase equivalents.