Skip to content
16-Week DSA Roadmap
LeetCode #125EasyProblem 1 of 8

Valid Palindrome

Decide whether a sentence reads the same forwards and backwards once you ignore spaces, punctuation and capital letters.

  • Converging two pointers

Before this, know: Strings and indexes, Loops (while)

The problem in plain English

A palindrome is a word or sentence that reads the same forwards and backwards, like “level” or “racecar”.

You get a string s (a piece of text). Return true if it is a palindrome and false if it isn’t. There’s a twist: before checking, we ignore everything that isn’t a letter or a digit (spaces, commas, !, : …), and we treat capital and small letters as the same (“T” counts as “t”).

A string is really just a row of characters, each with an index (its position, starting at 0). Here is s = "Taco cat!":

s
  1. T0
  2. a1
  3. c2
  4. o3
  5. ␣4
  6. c5
  7. a6
  8. t7
  9. !8
Ignore the space and the '!' and lowercase the T: what's left is 'tacocat', which reads the same both ways. Answer: true.

(We draw a space as ␣ so you can see it.) The rules that matter:

  • Only letters and digits count. Digits matter too: "0P" is not a palindrome.
  • Upper and lower case are the same letter.
  • A string with no letters or digits at all (like " ") counts as a palindrome. An empty string reads the same both ways.

Before you code: think it through

Those two fingers are what programmers call pointers: variables that remember a position in the string. We’ll call them left and right.

  1. l0
  2. e1
  3. v2
  4. e3
  5. l4
Compare the outside pair first, then move both pointers one step inward.

Pause and think

In 'level', the left pointer starts at index 0 and the right at index 4. After the first pair matches, where are they? When do we stop?

Approach 1: Clean, reverse, compare

The most direct idea: build a new string that keeps only the letters and digits (in lowercase), then check whether that string equals its own reverse.

Clean, reverse, compare

s = "Taco cat!"

s
  1. T0
  2. a1
  3. c2
  4. o3
  5. ␣4
  6. c5
  7. a6
  8. t7
  9. !8
cleaned (a new copy)
  1. empty
  • Looking at now
  • Left out
  • Just copied
  • Same in both copies
  • Different

Plan: copy only the letters and digits into a new string called "cleaned" (in lowercase), then compare it with its own reverse.

Step 1 / 12

Which line is running?

function isPalindrome(s) {  let cleaned = "";Running now:   for (const ch of s) {    if (/[a-z0-9]/i.test(ch)) {      cleaned += ch.toLowerCase(); // keep letters and digits only    }  }  const reversed = cleaned.split("").reverse().join("");  return cleaned === reversed;}

Clean, reverse, compare

function isPalindrome(s) {  let cleaned = "";  for (const ch of s) {    if (/[a-z0-9]/i.test(ch)) {      cleaned += ch.toLowerCase(); // keep letters and digits only    }  }  const reversed = cleaned.split("").reverse().join("");  return cleaned === reversed;}
def is_palindrome(s):    cleaned = ""    for ch in s:        if ch.isalnum():            cleaned += ch.lower()  # keep letters and digits only    reversed_text = cleaned[::-1]    return cleaned == reversed_text

This gives the right answer, and in an interview it’s a perfectly good first thing to say. In Python, cleaned[::-1] is a short way to write “the string backwards”.

Why isn’t it ideal?

It’s not slow: we read every character a few times, so the work grows in step with the length of the string. We describe that with Big-O notation, a way to say how work grows with input size: this is O(n) time, where n is the number of characters.

The cost is memory. We build two brand-new strings: cleaned and its reverse. For "Taco cat!" that’s 7 + 7 = 14 extra characters. For a string of 200,000 characters (LeetCode’s limit), it can be 400,000 extra characters. That’s O(n) extra space. The interviewer will usually ask: “Can you do it without making a copy?”

The pattern: converging two pointers

Instead of copying, we can read the original string from both ends at the same time, skipping the characters that don’t count as we go.

Pattern

Converging two pointers

Template

Use it when: you need to compare or pair up items from both ends of an array or string, such as checking symmetry.

Signal words

  • “palindrome”
  • “reads the same backward”
  • “reverse”
  • “compare from both ends”
  • “in-place, O(1) extra space”

Approach 2: Two pointers from both ends

  1. Put left on index 0 and right on the last index.
  2. While left is smaller than right:
  3. Move left to the right past anything that isn’t a letter or digit. Do the same for right, moving left.
  4. Compare s[left] and s[right] in lowercase. If they differ, return false.
  5. If they match, move both pointers one step inward and repeat.
  6. If the loop ends, every pair matched: return true.

Press Play, or click the player and use the arrow keys. Watch the grey boxes: those are characters we skip without ever copying anything. Then try the edge cases: a string that is only a space, and "0P", where a digit decides the answer.

Two pointers from both ends

s = "Taco cat!"

s
  1. T0
  2. a1
  3. c2
  4. o3
  5. ␣4
  6. c5
  7. a6
  8. t7
  9. !8
variables
left
0
right
8
s[left] vs s[right]
—
result
—
  • Skipped (not a letter or digit)
  • Pair matches
  • Pair differs / being skipped
  • Already matched

Put one pointer on each end: left at index 0 and right at index 8. A palindrome reads the same from both ends, so we compare the outside pair first and walk inward.

Step 1 / 12

Which line is running?

function isPalindrome(s) {  let left = 0;Running now:   let right = s.length - 1;  while (left < right) {    while (left < right && !isAlnum(s[left])) left++; // skip junk on the left    while (left < right && !isAlnum(s[right])) right--; // skip junk on the right    if (s[left].toLowerCase() !== s[right].toLowerCase()) {      return false;    }    left++; // they match: move both pointers inward    right--;  }  return true;}function isAlnum(ch) {  return /[a-z0-9]/i.test(ch); // a letter or a digit?}

Notice that the skipping loops also check left < right. Without that check, a string made only of punctuation would let left run off the end of the string.

The code, line by line

Two pointers from both ends

function isPalindrome(s) {  let left = 0;  let right = s.length - 1;  while (left < right) {    while (left < right && !isAlnum(s[left])) left++; // skip junk on the left    while (left < right && !isAlnum(s[right])) right--; // skip junk on the right    if (s[left].toLowerCase() !== s[right].toLowerCase()) {      return false;    }    left++; // they match: move both pointers inward    right--;  }  return true;}function isAlnum(ch) {  return /[a-z0-9]/i.test(ch); // a letter or a digit?}
def is_palindrome(s):    left, right = 0, len(s) - 1    while left < right:        while left < right and not s[left].isalnum():            left += 1  # skip junk on the left        while left < right and not s[right].isalnum():            right -= 1  # skip junk on the right        if s[left].lower() != s[right].lower():            return False        left += 1  # they match: move both pointers inward        right -= 1    return True

On LeetCode, JavaScript gives you var isPalindrome = function(s) { … } and Python wraps the function in class Solution as def isPalindrome(self, s). The body is the same as ours.

  • Line 1: define the function. It takes the string s.
  • Lines 2–3 (JS) / line 2 (Python): the two pointers. left starts on the first character (index 0) and right on the last one (index length − 1, because indexes start at 0).
  • Line 4 (JS) / line 3 (Python): keep going while left is still to the left of right. When they meet or cross, every pair has been compared.
  • Line 5 (JS) / lines 4–5 (Python): skip characters on the left that aren’t letters or digits. isAlnum is our small helper at the bottom (JS, lines 16–18): /[a-z0-9]/i is a pattern that matches one letter or digit, and the i means “ignore case”. In Python, strings already have .isalnum() (“is alphanumeric”, meaning a letter or a digit).
  • Line 6 (JS) / lines 6–7 (Python): the same skipping on the right side.
  • Line 7 (JS) / line 8 (Python): compare the two characters in lowercase (toLowerCase() / .lower()), so “T” and “t” count as equal.
  • Line 8 (JS) / line 9 (Python): one mismatch proves it’s not a palindrome, so return false straight away.
  • Lines 10–11: both languages. The pair matched, so move both pointers one step inward.
  • Line 13 (JS) / line 12 (Python): the loop finished without a mismatch, so the answer is true.

Dry run

Let’s trace s = "Taco cat!". Indexes: T=0, a=1, c=2, o=3, space=4, c=5, a=6, t=7, !=8.

stepleftrightwhat happens
108s[8] = '!' is not a letter: right moves to 7
207compare 'T' and 't': equal (ignoring case), move inward
316compare 'a' and 'a': equal, move inward
425compare 'c' and 'c': equal, move inward
534s[4] is a space: right moves to 3
633left = right: 'o' matches itself, move inward
742left > right: the loop stops, return true
s = "Taco cat!"

Step 5 is the interesting one: the space sits between the two halves. The right pointer skips it and lands on the same spot as the left pointer, which is why the skipping loop needs the left < right check.

Complexity

Clean, reverse, compare

Time

O(n)

We read each character a constant number of times: once to clean, once to reverse, once to compare.

Space

O(n)

Two new strings, each up to n characters long.

Two pointers from both ends

Time

O(n)

Every step moves left or right closer to the other, so together they make at most n moves. Double the text, double the work.

Space

O(1)

Just two numbers, left and right, however long the string is. O(1) means 'a fixed amount'.

Both are equally fast; the two-pointer version wins on memory, and that’s the point interviewers are looking for.

Common mistakes and edge cases

What to say out loud, in this order:

  1. Confirm the rules: “Only letters and digits count, and case doesn’t matter?”
  2. Give the simple version first: “I could build a cleaned copy and compare it with its reverse. That’s O(n) time but O(n) extra space.”
  3. Improve it: “Instead, I’ll use two pointers from both ends and skip non-alphanumeric characters in place. Same O(n) time, O(1) space.”
  4. Mention the edge cases: digits, a string with no letters, and the pointers crossing.

Likely follow-up questions:

  • “What if you may delete at most one character?” That’s Valid Palindrome II (LeetCode #680): on the first mismatch, try skipping the left character or the right one, and check the rest with the same two-pointer loop.
  • “Can you do it without a regular expression?” Yes: check the character codes ('a' to 'z', 'A' to 'Z', '0' to '9') yourself.

Related problems:

  • Two Sum II (next problem): the same “one pointer at each end” idea, but the pointers move based on a sum.
  • Container With Most Water (week 2): two pointers from both ends, choosing which one to move.
  • The week 2 overview has the general template for converging two pointers.