Valid palindrome

Lesson 2.3 · Easy · Opposite ends · 6 min · by Vinay C

We'll cover the following

Check whether a string reads the same both ways, ignoring punctuation and case.

Watch it run

Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.

23 items · 14 steps
La0
b1
c2
,3
d4
e5
f6
,7
g8
h9
i10
,11
i12
h13
g14
,15
f16
e17
d18
,19
c20
b21
Ra22

"a" matches "a". Move both inward.

1 / 14

The idea

Complexity

TimeSpaceWhy
O(n)O(1)Each character is looked at once from one side.

In Python

def is_palindrome(s):
    l, r = 0, len(s) - 1
    while l < r:
        if not s[l].isalnum(): l += 1
        elif not s[r].isalnum(): r -= 1
        elif s[l].lower() != s[r].lower(): return False
        else: l += 1; r -= 1
    return True

Summary: say it in the interview

  • Compare the two ends and walk inward. Skip anything that is not a letter or digit. One mismatch is enough to stop.
  • Time O(n), space O(1). Each character is looked at once from one side.