isPalindrome()

A common interview question to ask junior engineers (or so I’ve heard) is some variation of, given a word or sentence, determine whether or not said word or sentence is a valid palindrome. There are many different ways to go about solving this, but today I’ll cover two different approaches to the most basic, single word version, of this problem.

So first things first, what is a palindrome? According to Dictionary.com it’s “a word, phrase, or sequence that reads the same backward as forward”. “refer” and “racecar” are both examples of palindromic words. Read them right to left and you have the same words as if you were to read them left to right. Before jumping into solving any problem during a technical interview, you should always get clarification on anything that might be vague or unclear. For example, are we considering an empty string a valid palindrome? What if the string contains capital letters? Should we treat those as equal to their lowercase counterparts, and if so, how will we handle these cases and work that into our solution? For the sake of the solutions we’ll walk through here, we’ll assume that we’re given a lowercase string without any extra spaces at the beginning or end, and that an empty string is in fact a valid palindrome.

.split().reverse().join()

Because a palindrome is the same forwards and backwards, one way of determining whether a string is a palindrome is to check and see if the reversed version of the original string is the same as the original string. This is easy enough to do using built in Javascript methods. Javascript provides a .reverse() method, BUT, it only works on arrays. It reverses an array in place, so the last element becomes the first, the second to last becomes the second, etc. In order to utilize this method to help reverse our string, we’ll first need to turn our string into an array of characters. This can of course be done iteratively by creating a new array, looping through the string, and pushing each character into the array, but we’re using built in methods in this solution, and lucky for us, Javascript provides us with a .split() method. This method divides a string into an ordered list of substrings, and takes optional separator, and limit arguments. This separator argument is what the string will be split on, and the only one we’ll need to pass in here. According to the Mozilla documents, “When found, separator is removed from the string, and the substrings are returned in an array”. Because we’re dealing with a single string, we can pass “” as the separator argument. This will return an array with each element a character of our string, which we can now call .reverse() on. This will give us an array of our string characters reversed, which we can call the .join() method on. This will rejoin our array of reversed characters into a string. .join() also takes an optional separator argument, which according to Mozilla, “Specifies a string to separate each pair of adjacent elements of the array.” Since we want a single string with no spaces or additional characters, we will pass “” as the separator argument. This method will return true for an empty string (our edge case), so we don’t need to worry about handling this separately, and can simply return whether or not the reversed string is the same as the original. The code is as follows:

Two Pointers Technique

The second method forgoes built in Javascript methods for a while loop. When you look at a palindrome, you’ll see that the first letter is the same as the last, the second letter is the same as the second to last, etc. We can utilize a technique called two pointers to essentially look at two of the letters in our string at once and see if they’re the same. Since we know that each letter and it’s opposite (in terms of placement in the string) should be equal, we can set up two pointers, one of which will start from index 0, or the beginning of the string, and move forwards towards the middle, the second of which will start from the last index of the string, or the end, and move backwards towards the middle. On every set of characters, we want to check and see if they’re the same. If they are, then we want to increment the index of the forward moving pointer by one, and decrement the index of the backward moving pointer by one, and repeat the check for the next set of characters. To make sure we don’t end up with an endless loop, we only want and need to keep doing this while the index of the forward moving pointer is less than the index of the backward moving pointer. If at any of the checks the two letters aren’t equal, we’ll know that the string can’t be a palindrome, and we can return false. If we are able to fully complete the while loop without hitting this return false statement, then we’ll know our string is a valid palindrome, and we can return true after our while loop. Again, an empty string will return true here without needing to separately handle this case. This is because, the length of an empty string is 0. As you’ll see below, we set the start variable to 0, and the end variable to str.length — 1. Since the length of an empty string is 0, str.length — 1 of an empty string will be -1. We’ll never actually enter the while loop and will go directly to the return true statement, giving us the following solution:

In terms of which of these solutions is “better”, let’s have a look. The first method, .split().reverse().join() creates an additional array (from the .split() method) and creates a new string (from the .join() method), both of which add to the memory usage of this solution. Because these structures have to be large enough to accommodate all characters of the input string, as the length of the string we input grows, the more space these structures will require in memory to store this additional data. In terms of time, I will not pretend to fully understand how these built in methods work under the hood, but I would imagine each would require going through either the string, or array of characters, once, again changing linearly as the input size grows.

The second solution doesn’t require the creation of any new data structures that are dependent on our input, and thus requires less space in memory. Our worst case scenario in terms of time complexity is that we do in fact have a palindrome, and have to go through every character in our string to come to this conclusion (while technically we’re only ever looping half the number of times as there are letters in the string, the number of times we need to loop will still increase proportionately to the size of our input). This means that as our input size increases, so will the time it takes to run our algorithm, making this linear time complexity as well. So which is “better” to use in a real life program? It really just depends. Sure, the first solution has a worse space complexity, but it’s far more concise and perhaps easier for someone unfamiliar with your code base to read and understand. If you know that you have limited space on the machine you’re running your program, maybe the second option is the better choice.