Skip to content
ReadMe Daily

Search articles, problems, patterns and every cheat sheet topic.

Valid Palindrome

Check whether a string reads the same forwards and backwards, ignoring case and punctuation, using two pointers in O(n) time and O(1) space.

easyPattern: Two Pointers

Updated Quick read: 3 min read

Approaches at a glance

ApproachTimeSpace
Clean, reverse and compareO(n)O(n)
Two pointersO(n)O(1)

The problem

A string is a palindrome if it reads the same forwards and backwards once you ignore upper and lower case and skip every character that is not a letter or digit. Return true if the given string is a palindrome.

"A man, a plan, a canal: Panama"   →  true    ("amanaplanacanalpanama")
"race a car"                       →  false   ("raceacar")
" "                                →  true    (nothing left to compare)

Approach 1: clean, reverse and compare

Build the cleaned string, reverse it, and check that the two are equal.

JavaScript

function isPalindromeReversed(text) {
  const cleaned = text.toLowerCase().replace(/[^a-z0-9]/g, "");
  const reversed = [...cleaned].reverse().join("");
  return cleaned === reversed;
}

Python

def is_palindrome_reversed(text):
    cleaned = "".join(ch.lower() for ch in text if ch.isalnum())
    return cleaned == cleaned[::-1]

This is short and clear. Its cost is memory: it creates a cleaned copy and a reversed copy of the input.

Time O(n). Space O(n).

Approach 2: two pointers

A palindrome's first character matches its last, its second matches its second-to-last, and so on. So compare from both ends and move inwards, with no copies at all. This is the opposite-ends form of the two pointers pattern.

JavaScript

function isLetterOrDigit(ch) {
  return /[a-z0-9]/i.test(ch);
}
 
function isPalindrome(text) {
  let left = 0;
  let right = text.length - 1;
 
  while (left < right) {
    if (!isLetterOrDigit(text[left])) {
      left++;
    } else if (!isLetterOrDigit(text[right])) {
      right--;
    } else {
      if (text[left].toLowerCase() !== text[right].toLowerCase()) return false;
      left++;
      right--;
    }
  }
  return true;
}

Python

def is_palindrome(text):
    left = 0
    right = len(text) - 1
 
    while left < right:
        if not text[left].isalnum():
            left += 1
        elif not text[right].isalnum():
            right -= 1
        else:
            if text[left].lower() != text[right].lower():
                return False
            left += 1
            right -= 1
    return True

Each turn of the loop does exactly one thing: skip a character on the left that does not count, skip one on the right, or compare a pair and move both pointers.

Walkthrough

"race a car":

left right Characters Action
0 9 r, r Match, move both
1 8 a, a Match, move both
2 7 c, c Match, move both
3 6 e, space Skip the space on the right
3 5 e, a Different: return false

Time O(n): each pointer crosses the string at most once. Space O(1): only two indexes.

Try it yourself

Copy a solution from above, add the lines below, and run it. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python.

JavaScript

console.log(isPalindrome("A man, a plan, a canal: Panama")); // true
console.log(isPalindrome("race a car")); // false

Python

print(is_palindrome("A man, a plan, a canal: Panama"))  # True
print(is_palindrome("race a car"))  # False

The comment after each line is the result you should see.

Common mistakes

  • Forgetting digits. Digits count as valid characters; only spaces and punctuation are skipped.
  • Looping with left <= right. When the pointers meet on the middle character there is nothing to compare it with. left < right is enough.
  • Comparing before lowercasing. "A" and "a" must be treated as equal.

Original problem: LeetCode 125: Valid Palindrome