Start learning free

LESSON 225 OF 348 · TWO POINTERS

Palindrome Check in TypeScript: Two Pointers in O(n) Time and O(1) Space

Practice O(n) Read the full explanation

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.


Hints:

For the string to be a palindrome, for each character, there is a corresponding element which should be equal to that one:
  • s[0] == s[n - 1]
  • s[1] == s[n - 2]
  • s[2] == s[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 throught the algorithm?

For as long as i < j:
  • 1. We should check if s[i] != s[j] 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

    TYPESCRIPT · TWO POINTERS

    Palindrome Check in TypeScript, explained

    Problem overview

    The method isPalindrome receives a string, input, and returns true when it reads the same forwards and backwards, and false otherwise. The comparison is exact: every character counts, including spaces, and uppercase and lowercase letters are different characters.

    In the first example, "madam racecar madam", the first and last characters are both m, the second and second-to-last are both a, and so on, all the way to the space in the middle. The answer is true. In the second, "abcbx", the first character is a and the last is x, so the answer is false.

    The statement asks for O(n) time and O(1) extra space.

    Approach: compare from both ends toward the middle

    A string is a palindrome when the character at position k equals the character at position n - 1 - k, for every k. Each pair needs checking once, and the middle of the string pairs with itself.

    A tempting shortcut is to build the reversed string and compare it with the original. That works, but it creates a second string of length n, which costs O(n) extra space. The statement asks for constant extra space, so the check should work directly on the original string.

    The way to do it is with two pointers. One starts at the first character and the other at the last. While they haven't met, compare the two characters. If they differ, the string can't be a palindrome and the method can stop. If they match, move both pointers one step toward the middle and repeat.

    Here is "abcba":

    left = 0, right = 4: 'a' and 'a' match
left = 1, right = 3: 'b' and 'b' match
left = 2, right = 2: the pointers met, the loop stops

    Every pair matched, so the result is true. The middle character, c, is never compared. That is fine, because it is its own mirror image.

    Step by step

    1. Create the left pointer, a number named left, starting at 0, the first index. It changes in the loop, so it is declared with let.
    2. Create the right pointer, right, starting at input.length - 1, the last index. Indices start at 0, so the last one is one less than the length.
    3. Loop while left < right. As long as the pointers haven't met or crossed, there is a pair left to compare. For an odd length, they meet on the middle character and the loop ends.
    4. Compare the pair. If input[left] !== input[right], return false right away. One mismatched pair is enough to decide.
    5. Move the pointers: increase left and decrease right. Without this, the loop would compare the same pair forever.
    6. Return true after the loop. This line is reached only when every pair matched.

    The solution in TypeScript

    class Solution {
    isPalindrome(input: string): boolean {
        let left: number = 0;
        let right: number = input.length - 1;
        while (left < right) {
            if (input[left] !== input[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

    The TypeScript details worth knowing:

    • Indexing a string. input[left] gives a one-character string. Strings are read-only: you can read input[0], but you can't assign to it. That is why the code reads from the original instead of rearranging it.
    • !== is strict inequality. It compares without converting types, and is the form to use in TypeScript. With two strings it is true when their contents differ.
    • The annotations number and string. They are checked by the compiler and removed when the code is compiled to JavaScript. They don't change what runs.
    • UTF-16 units. A string's indices count UTF-16 code units, and some characters, such as many emoji, take two. For plain text like the examples this makes no difference, but such characters would be split into halves by the pointer approach.

    Complexity

    Time: O(n). Each pass of the loop moves the pointers two positions closer, so there are at most n / 2 passes, and each does constant work.

    Space: O(1). The method keeps two numbers, no matter how long the string is.

    Edge cases and common mistakes

    • Empty string. "" has right = -1, so the loop never runs and the result is true. An empty string reads the same in both directions.
    • One character. "a" starts with left = right = 0, so no pair is compared and the result is true.
    • Case and spaces count. "Madam" gives false, because M and m are different characters. "ab ba" gives true, with the space as the middle character. The method doesn't ignore punctuation or spaces.
    • Using left <= right. It would also compare the middle character with itself, which always matches. The result stays right, but the extra pass is not needed.
    • Forgetting to move the pointers. The loop would then never end, as long as the first pair matches.
    • Comparing a reversed copy. It gives the right answer but uses O(n) space, which the statement rules out.

    Testing

    • "madam racecar madam" gives true.
    • "abcbx" gives false.
    • "" gives true.
    • "a" gives true.
    • "Madam" gives false.
    • "ab ba" gives true.
    Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free