Valid Palindrome

Easytwo pointersMetaMicrosoftApple

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.

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

Examples

Input:s = "A man, a plan, a canal: Panama"

Output:true

Explanation:"amanaplanacanalpanama" is a palindrome.

Input:s = "race a car"

Output:false

Explanation:"raceacar" is not a palindrome.

Input:s = " "

Output:true

Explanation:After removing non-alphanumeric characters, s is an empty string. An empty string is a palindrome.

Constraints

1 <= s.length <= 2 * 10^5
s consists only of printable ASCII characters

💡 Hints

Hint 1

Use two pointers starting from both ends of the string.

Hint 2

Skip non-alphanumeric characters and compare lowercase versions.

Algorithm Complexity

Official asymptotic Big-O runtime and auxiliary memory analysis

Linear

Algorithmic Approach

Two pointers from both ends. Skip non-alphanumeric characters, then compare lowercase characters. If any mismatch, return false.

Time ComplexityO(n)

Why:

Two pointers move toward each other from the ends, skipping non-alphanumeric characters and comparing at most n characters.

Space ComplexityO(1)

Why:

Directly inspects characters in-place using two pointer indices without allocating a cleaned string copy.

Big-O Growth CurveLinear (O(N))

Execution time scales directly in proportion to the input size.

🌍 Real-World Use Cases

MetaUsername validation

Checking if usernames or display names have palindromic patterns, used in content moderation to detect spam patterns.

GoogleDNA sequence analysis

Identifying palindromic sequences in DNA strands, which form hairpin structures important in molecular biology.

🔍 Dry Run

Solution⏱ O(n) | 💾 O(1)

Line2

left=0number

right=7number

Initialize left=0 (→ 'r') and right=7 (→ '!'). Input: "racecar!"