mafeshsho8lmafeshsho8l
Get Started
All coding questions

Valid Palindrome

easy
Blind 75NeetCode 150stringstwo-pointers

Problem

Given a string, decide whether it reads the same forwards and backwards once you ignore case and consider only alphanumeric characters. Return true if it is such a palindrome.

Examples

Input: s = "A man, a plan, a canal: Panama"
Output: true
Ignoring punctuation and case it is a palindrome.
Input: s = "race a car"
Output: false
Reading the cleaned letters backwards differs.

Constraints

  • • 1 <= s.length <= 2 * 10^5
  • • String contains printable ASCII characters
Hints(tap to reveal)
  • 1. Two pointers from each end converge.
  • 2. Skip characters that are not letters or digits.
Optimal approach(spoiler)
  1. Place one pointer at the start and one at the end.
  2. Advance each pointer past any non-alphanumeric character.
  3. Compare the two characters case-insensitively.
  4. On any mismatch return false; otherwise move both inward.
  5. O(n) time, O(1) space.

Ready to solve it?

Write your solution in the editor and get an instant AI grade on correctness, edge cases, and complexity.

Practice in the editor