vizlearn

Check whether a string is a palindrome

Interview QuestionsBy Updated

s == s[::-1] is the one-liner and allocates a reversed copy. The O(1)-space answer walks two pointers inwards, each skipping non-alphanumeric characters, comparing case-folded. It also short-circuits on the first mismatch, which the one-liner cannot.

Overview

The one-liner and its cost

s == s[::-1] is correct and reads well. It builds a full reversed copy first, so it is O(n) extra memory, and it always compares the entire string even when the first and last characters already disagree.

Cleaning first — clean = "".join(c.lower() for c in s if c.isalnum()) then comparing — is readable and costs a second full copy on top.

StringsCoding problemEasy

Step through it

What to watch

  • Commas and spaces are skipped, not stripped into a new string.
  • Both skip loops need the lo < hi guard.
  • A mismatch stops immediately — no need to check the rest.

Say this out loud

"Two pointers from both ends, skip anything that isn't alphanumeric, compare lowercased. O(n) time, O(1) space, and it bails on the first mismatch."

Check whether a string is a palindrome

Check whether a string is a palindrome, ignoring punctuation and case.

The two-pointer version

One pointer at each end. Advance each past anything that is not alphanumeric, compare the two characters case-folded, then step both inwards. No copy is made and the first mismatch ends it.

The subtlety is the guards: both inner skip loops need lo < hi in their condition, or a string of pure punctuation runs a pointer off the end. That is the bug this question is really probing.

The follow-up

"Now allow one character to be deleted." On a mismatch, try skipping the left character or the right one and check whether either remaining span is a plain palindrome. That is still O(n): you only get one chance to branch, so the two checks do not nest.

Run it in Python

Both approaches on the same inputs, with the comparison counts printed — which is where the two-pointer version's short-circuit shows up. The last section is the delete-one follow-up.

palindrome.pyPython 3
Output
How the code works
  1. while lo < hi and not s[lo].isalnum():The guard is the whole trick. Without lo < hi in the inner condition, a string of pure punctuation walks a pointer straight off the end.
  2. s[lo].lower() != s[hi].lower()Case folding happens at the comparison, so no cleaned copy is ever built. casefold() is the more correct choice for non-English text.
  3. return False, comparedThe short-circuit. "race a car" is settled by the first pair; the slice version compares everything regardless.
  4. plain(lo + 1, hi) or plain(lo, hi - 1)The delete-one follow-up. Only one branch is ever taken, so the two checks do not nest and the whole thing stays O(n).
Change one thing
  • Feed it ".,!?". Both return True and the two-pointer version does it without allocating — check the guards are why.
  • Drop lo < hi from one inner loop and run the punctuation-only case. The IndexError is what the guard prevents.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.


    



Check yourself
0 of 3
Answer without scrolling back up.
  1. The main advantage of the two-pointer palindrome check over s == s[::-1] is:
  2. Why do the inner skip loops need `lo < hi` in their condition?
  3. In the 'allow one deletion' variant, why is it still O(n)?





 Cheat sheet
Check whether a string is a palindrome
s == s[::-1] is the one-liner and allocates a reversed copy. The O(1)-space answer walks two pointers inwards, each skipping non-alphanumeric characters, comparing case-folded. It also short-circuits on the first mismatch, which the one-liner cannot.
INTERVIEW · vizlearn.in/interview/valid-palindrome.html
More in Interview
InterviewAre two strings anagrams?InterviewGroup anagrams togetherInterviewLongest substring without repeating charactersInterviewFirst non-repeating character
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact