Valid Palindrome

Asked byFacebookAmazonMicrosoftAppleAdobeBloomberg

Problem

Given a string s, determine whether it reads the same forward and backward after converting all uppercase letters to lowercase and removing all non-alphanumeric characters.

Examples

Example 1

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

Output:true

Example 2

Input:s = "race a car"

Output:false

Constraints

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

Solve it in the editor. Sign in free to run your Python or JavaScript against test cases, get a verdict, and track your attempts.

Solve on FeatCode →

How to approach it: the Two Pointers pattern

Two indices move through a sorted (or sortable) structure — often from opposite ends or at different speeds — to avoid the nested loops a brute-force scan would need.

Look for this pattern when

The input is sorted, or can be sorted without losing information you need.
You're looking for a pair, triplet, or partition that satisfies a sum or comparison condition.
You need to compare values from both ends of a sequence (e.g. palindrome checks).

Read the full Two Pointers guide →

Video walkthroughs

Original problem on LeetCode ↗