colinthornton/blog

Palindrome Algorithms in JavaScript

May 15, 2020

This post goes in depth into my thought process when solving algorithm problems. There will be code. The code will be written in JavaScript. If that doesn’t appeal to you then turn back now.

If you’re a beginner coder, then I hope this post will help you gain some insight into how to tackle algorithms. If you’re unfamiliar with JavaScript, I hope you’ll be able to pick up some new syntax or built-in methods and add them to your repertoire. If you’re already a JavaScript expert and leetcode master, then I encourage you to message me about what areas I could improve.

Defining the problem

If you’re not familiar, a palindrome is a word or phrase that retains its spelling even when reversed, the quintessential example being “race car.” Go ahead, confirm that it’s a palindrome. You can flip it around however many times you like, the letters will always come in the same order: r-a-c-e-c-a-r.

I’m not quite sure why, but as far as algorithm problems go, this one comes up quite often. One thing I do know is that depending on the language you code it in, there are many approaches that you could take, so it’s good to keep the space and time complexity of your solution in mind (as with all algorithms).

I’m going to go over several solutions in JavaScript. The function signature looks like this:

/**
 * @param {string} str
 * @return {boolean}
 */
function isPalindrome(str) {}

A simple (and inefficient) solution

Let’s start with an approach that is easy to understand conceptually. The thought process goes like this: we need to determine whether str is the same as itself reversed, so why not start by reversing it?

So how can we reverse a string? A decrementing for loop could do the trick.

let reversed = "";
for (let i = str.length - 1; i > -1; i--) {
  reversed += str[i];
}

That’s all well and good, but we have to use let in order to reassign reversed for each character in str. I prefer to avoid reassignment when possible to help with readability and reduce the mental load of having to follow all the mutations of a variable.

Here’s a way to reverse it all in one line, chaining together some built-in string and array methods.

const reversed = str.split("").reverse().join("");

In case you’re unfamiliar, split is a string method that returns an array of strings generated by splitting the parent at each occurrence of the specified delimiter. reverse does what it says on the tin, it reverses the sorting of an array. Then join is the opposite of split, it turns an array of strings into a single string, connecting those array elements together with the specified delimiter. In our case, the delimiter is an empty string, so str will be turned into an array of single-character strings, reversed, then joined back together again.

Now that we have reversed, we can simply compare it to str, and we have our solution. If they’re the same, it’s a palindrome. Altogether, here’s the solution.

function isPalindrome(str) {
  const reversed = str.split("").reverse().join("");
  return str === reversed;
}

One thing this solution really has going for it is readability. Two lines and you’re done - does str equal itself reversed? It can’t get much easier to understand than that. But, you may have noticed that I titled this section in a way that implies it’s not very good. So what gives?

The biggest issue with this approach is the amount of space it requires. When the function is called, the computer already has space carved out in memory to store str, and then it needs to carve out another equally large chunk of memory to store reversed. In the case of an input like “racecar” it’s trivial, but imagine the input string were the entire text of some novel you picked up off the shelf. Chances are good that if you looked at the first letter of the first word of the book, then looked at the last letter of the last word, that they are not the same. There’s no reason to even look at any of the other letters, you can definitively determine that the novel’s text is not a palindrome right there. But with the algorithm above, we store a reversed copy of all the characters in memory, just in case!

Let’s see if we can’t reduce our memory requirements.

No copies

This time we’re going to write isPalindrome without a reversed variable. It would be ideal if we could solve the problem only using the string that’s been passed to us.

I already hinted at the algorithm we’re going to use in the paragraph above about the case of a very long input string. If you were to pick up a book and determine if its text were a palindrome, you’d start by looking at the first letter and comparing it to the last letter. If they were the same, you’d go to the second letter and compare it to the second-to-last letter, and so on… If you miraculously reached the end of the book without finding a mismatch, then congratulations, that novel’s a palindrome (and you have a lot of time on your hands).

Let’s try to emulate that approach in code. In order to loop through each character in the string, we’re going to use a for loop, comparing the front index of str to the corresponding back index along the way. In the case that they aren’t the same, we can immediately return false without wasting time checking the rest of the characters.

for (let front = 0; front < str.length; front++) {
  const back = str.length - 1 - front; // `front` places from the back
  if (str[front] !== str[back]) {
    return false;
  }
}

This is already starting to look good. But you may have noticed that there is one small optimization that can be made. In the current implementation, once the loop passes the halfway-point, it starts to make the same comparisons over again, just with front and back swapped. If it never finds a mismatch, then each pairing will end up being checked twice. So the optimization is to stop the loop once it has reached the midpoint of the string, because it’s definitely a palindrome if the loop makes it there.

for (let front = 0; front < str.length / 2; front++) {
  // same as above
}

Now front will increment from index 0 while back decrements from the last index, and they’ll eventually meet at the midway point.

The final solutions looks like this:

function isPalindrome(str) {
  for (let front = 0; front < str.length / 2; front++) {
    const back = str.length - 1 - front;
    if (str[front] !== str[back]) {
      return false;
    }
  }
  return true;
}

Leveling up

The algorithms above work on the assumption that all characters are counted the same, including spaces, punctuation, and capitalization. But what if I only wanted to look at the spelling of the word or phrase. For example, what if we wanted our algorithm to count all of the following as valid palindromes?

race car
racecar
Race Car
rAcEcAr!!!!
r!a@c#e$c%a^r
r      a     ce car

Now we’re going to have to go back to the drawing board.

Let’s start again with the opposed indexes approach, tracking two indexes that move from opposite ends toward the middle of the string. But we’ll need to make a modification here. With an input like r a c ecar, the midway point of the string is not the midway point of the letters (‘e’). Since we can’t be sure about the midway point of the actual letters we care about, we’ll use a while loop instead of a for loop, which will allow us to have more control over updating the indexes.

// runs the same as the for loop above
let front = 0;
let back = str.length - 1;
while (front < back) {
  if (str[front] !== str[back]) {
    return false;
  }
  front++;
  back--;
}

But now we’ve run into the first roadblock. In the case of race car, this algorithm will return false when comparing the letter “e” at index 4 with the space at index 5.

So we need to have a way to check if the character we’re looking at is a valid letter of the alphabet. This way we can ignore all non-alpha characters (spaces, punctuation, etc.). A regular expression should do the what we need.

const alpha = /[A-Za-z]/;

And now let’s modify the while loop so that it skips to the next index when it finds a non-alpha character.

while (front < back) {
  if (!alpha.test(str[front])) {
    front++;
    continue;
  }
  if (!alpha.test(str[back])) {
    back--;
    continue;
  }

  if (str[front] !== str[back]) {
    return false;
  }
  front++;
  back--;
}

The first two if blocks will increment front and decrement back until both of them are at an index containing a letter. Then those letters will be compared in the third if block, returning false if they’re not the same. If they are the same, then it goes on to the next set of characters and continues the loop.

Now we have handled all non-alpha characters, but we still haven’t handled capitalization. As I said before, I’d like Race car to count as a palindrome too. Let’s change the comparison at the end of the while loop so that it doesn’t account for case. This is simple enough to do by leveraging the string method toLowerCase() (although toUpperCase() could be used in the same way).

if (str[front].toLowerCase() !== str[back].toLowerCase()) {
  return false;
}

Putting it all together, here’s the final solution.

function isPalindrome(str) {
  const alpha = /[A-Za-z]/;

  let front = 0;
  let back = str.length - 1;
  while (front < back) {
    if (!alpha.test(str[front])) {
      front++;
      continue;
    }
    if (!alpha.test(str[back])) {
      back--;
      continue;
    }

    if (str[front].toLowerCase() !== str[back].toLowerCase()) {
      return false;
    }
    front++;
    back--;
  }
  return true;
}