Start learning free

LESSON 173 OF 348 · STRINGS

Palindrome Check in TypeScript: Compare with the Reversed String

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 2
    Ctrl + Enter to check

    TYPESCRIPT · STRINGS

    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. Every character counts, including spaces and capital letters.

    In the first example, "madam racecar madam" is a palindrome. Reading it from the end gives the same text, space included, so the answer is true. In the second example, "abcbx" starts with a and ends with x, so the answer is false.

    Approach: build the reverse, then compare

    A palindrome is equal to its own reverse. That sentence is already an algorithm: reverse the string, then check whether the result equals the original.

    TypeScript strings have no reverse method, but arrays do. The lesson chains three calls to go through an array and come back:

    1. split("") turns the string into an array with one character per element.
    2. reverse() reverses that array.
    3. join("") glues the elements back into a string.

    For "abcbx" the array goes from ["a", "b", "c", "b", "x"] to ["x", "b", "c", "b", "a"], and the joined string is "xbcba". That is different from the input, so the answer is false.

    Another way to solve this problem is the two-pointer technique, which compares the first character with the last, the second with the second to last, and so on, without building a second string. It needs only constant extra space, while this lesson's version trades that for shorter code and uses O(n) extra space for the reversed copy. Both take O(n) time.

    Step by step

    1. Build reversedInput. Chain split(""), reverse() and join("") on input. The result is a string, and TypeScript infers that type, so no annotation is needed.
    2. Return the comparison. input == reversedInput is already a boolean, true exactly when the two strings are the same. There is no need for an if that returns true in one branch and false in the other.

    The solution in TypeScript

    class Solution {
    isPalindrome(input: string): boolean {
        let reversedInput = input.split("").reverse().join("");
        return input == reversedInput;
    }
}

    The TypeScript details worth a closer look:

    • Method chaining. Each call returns a value that the next call uses: a string[] from split, the same array from reverse, and a string from join. TypeScript follows these types through the chain, which is why reversedInput needs no annotation.
    • reverse belongs to arrays. Writing input.reverse() is a compile-time error, because string has no such method. Splitting first is what makes it available.
    • reverse changes its array. It reverses the array in place and also returns it. That is safe here, because the array is a temporary one created by split. The original string is untouched, as strings can't change.
    • == and ===. For two strings they give the same answer. TypeScript doesn't allow comparing values of unrelated types such as a string and a number with either, so most code uses === by habit, and it would work in this solution too.
    • Case and spaces matter. The comparison is exact. "Aba" is not a palindrome here because A and a are different characters, and "ab ba" is, because the space sits in the middle.
    • Emoji. split("") cuts between 16-bit units, and a character such as an emoji takes two of them. Reversing the array swaps the two halves of each such character, so a string like "😀😀" gives false, although it reads the same in both directions. For the letters and digits used in the lesson this makes no difference.

    Complexity

    Time: O(n). Splitting visits each of the n characters once, reversing swaps about n / 2 pairs, joining visits each element once, and the comparison looks at up to n characters. These steps run one after another, so the total is O(n).

    Space: O(n). The array of characters and the reversed string each hold n elements. The statement mentions O(1) extra space, which is what the two-pointer approach achieves. This version doesn't meet that bound.

    Edge cases and common mistakes

    • Empty string. It equals its own reverse, so the answer is true.
    • One character. "a" is a palindrome.
    • Even and odd lengths. "abba" and "abcba" are both palindromes. There is no middle character to special-case when you compare against the whole reversed string.
    • Different case. "Aba" returns false. Making the check ignore case would change the problem.
    • Leaving out the separator. join() with no argument joins with commas, so "ab" would turn into "b,a", which never equals the input. Pass "".
    • Comparing the array. Two arrays are never equal under == unless they are the same object, even when their contents match. Compare the joined strings.

    Testing

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