Skip to content
LEETFLIX

Valid Palindrome

EasyTwo pointersString
Solve on LeetCode

Easy · two-pointer palindrome. Real solution for this problem — same player as the hand-authored deep-dives.

01

Problem

Read the prompt, flip through the examples, then steal the idea.

LeetCode 125. Valid Palindrome. The copyrighted prompt is on LeetCode. This page is a working two-pointer palindrome for this problem: editable input, Python, Go, and a step-by-step animation.

Constraints

  • —Player inputs are capped so the animation stays readable.
  • —Match LeetCode's own constraints when you submit there.

Examples

Input

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

Output

true

02

Solution

Python and Go. The walkthrough below runs this same code.

Approach 1Optimal▶ Animated

Skip junk, compare ends

Walk inward. Ignore anything that is not alphanumeric. Compare lowercased letters. A mismatch is a no; pointers crossing is a yes.

The string is a palindrome iff the filtered character stream reads the same forwards and backwards. Two pointers do that in one pass, no extra copy.

Algorithm

  1. lo, hi at the ends.
  2. Skip non-alphanumeric characters.
  3. Compare lowercased; mismatch → false. Else step in. Done when lo >= hi.
Time
O(n)
Space
O(1)
Solution.py
class Solution:    def isPalindrome(self, s: str) -> bool:        lo, hi = 0, len(s) - 1        while lo < hi:            if not s[lo].isalnum():                lo += 1                continue            if not s[hi].isalnum():                hi -= 1                continue            if s[lo].lower() != s[hi].lower():                return False            lo += 1            hi -= 1        return True
Watch this run

03

Interactive walkthrough

Playing “Skip junk, compare ends”. Edit the input, hit Run, then scrub.

Approach: Skip junk, compare ends

Loading animation…