Start learning free

LESSON 293 OF 501 · TWO POINTERS

Palindrome Check

Practice O(n)

Given a string, determine if it is a palindrome.

A palindrome is a word, number, phrase, or other sequence of characters which reads the same backward as forward.

Example 1:

Input:  "madam racecar madam"

Output: True

Example 2:

Input:  "abcbx"

Output: False

Note:

Your algorithm should run in O(n) time and use O(1) extra space (the two-pointer approach below achieves this).


Hints:

For the string to be a palindrome, for each character, there is a corresponding element which should be equal to that one:
  • the character at index 0 equals the character at index n - 1
  • the character at index 1 equals the character at index n - 2
  • the character at index 2 equals the character at index n - 3
  • ...
How can we check all these pairs of corresponding characters while traversing the string one time?

We can use two pointers! One index variable i starting from the beginning (i = 0) and one index variable j starting from the end of the string (j = n - 1). How should we move these pointers through the algorithm?

For as long as i < j:
  • 1. We should check if the characters at indices i and j are different, and if so, we conclude the string is not a palindrome and return False.
  • 2. Move i one step to the right.
  • 3. Move j one step to the left.
  • 4. Go to step 1.
If i became greater than or equal to j and we haven't returned False, then we can conclude the string is a palindrome and return True.

STEP 1 OF 6
    Ctrl + Enter to check