I have had a few technical interviews lately asking questions that are variations or actually include the palindrome question. This is why I thought it would be relevant to shed some light on how I learned to solve this interview question in the hopes that someone could benefit from how to solve it by reading how I did it.
As far as I know there are 4 ways of solving this question, but when I refer to the best or worst way I am referring to best and worst big-O notation in both time and space complexity. I should also note that I will be solving this problem in JavaScript.
The Problem
A typical string manipulation question, the palindrome question states that if given a string that is not empty, to write a function that will determine if the word or words is spelled the same forwards and backwards.
The final output to determine this could be true or false as anything in JavaScript has a truthy or falsy value anyways. This doesn’t necessarily mean that you have to return the boolean true or false each time however. In other words if you are trying to test an if condition in a function by saying that it needs to return some kind of specific answer, but the input given as an argument would not make it possible to return that answer, then it would return false if tested in a JavaScript console.
Worst way — Making a new reversed string
Approach Summary: The worst way would be to create a new string and go through each letter backwards from the original string to put every letter in reverse and then compare the two strings.
How to solve: We’ll start by defining the function’s name which it is determining if a string is a palindrome so it is named relevantly. Our input would be the string every time the function is called.
function isPalindrome(string) {
Next we’ll set a variable for our eventual reversed string:
const reversedString = ‘’
Now to go through the string itself to concatenate the reversed string we will make a for loop, but it will start from the last letter of the string (let i = string.length -1), then it will keep going until it reaches the first letter of the input (i>=0), and i which represents each index, will decrease every time it runs (i --).
for (let i = string.length -1; i>=0; i — ){
Now to put what goes inside the loop I am using the += operator to concatenate every letter into my empty string which will represent my first string backwards. String[i] represents each letter and it is important to remember that reversedString += string[i] is the same as reversedString = reversedString + string[i].
reversedString += string[i];
}
This next line will be written to return a truthy value where the original string is the same as the reversed string.
return string === reversedString
}
Altogether it looks like the following:
function isPalindrome(string) {
const reversedString = ‘’
for (let i = string.length -1; i>=0; i — ){
reversedString += string[i];
}
return string === reversedString
}
Where this solution fails to be the best would be the fact that it has a big-O notation of O(n^2) for time complexity, not the best on the charts, and O(n) on the space complexity side, pretty good. However this compared to the second solution, clearly shows the other solution having a better time and space complexity, which I will get into soon. The important takeaway to see here is this solution has a bad of a time complexity mainly because the program has to create a brand new string which takes longer.
Best way — Using the pointer system to compare the furthest left and right side
Approach Summary: On the other hand, the best way to solve this problem would be to define a left and right pointer and compare the letter that each is pointing to. Then using a while loop, while the right pointer is on the right and while the left pointer is on the left, if at any point in time the letters the pointers are pointing to are not the same then return false. Otherwise, return true.
How to solve: To begin solving this, it starts off the same way as the last to set up a function where we choose an appropriate name and the input is still the string given.
function isPalindrome(string) {
This time however we are going to set two variables to represent the left and right pointers. The left pointer will represent the first index of the string which starts at 0. To compliment the left, we have a right pointer set equal to the string’s length -1 which represents the furthest number on the right, or last index.
let leftPointer = 0
let rightPointer = string.length-1
Now using the while loop we will say that we want to run the following logic while the left pointer is on the left side compared to the right pointer.
while (leftPointer < rightPointer){
Our logic will contain an if condition that says that if the left letter is not the same as the right letter the first time the loop goes through, then return false. Which means that if our string was “abcbz” and if “a” was not the same as “z” then it would return false at this point.
if(string[leftPointer] !== string[rightPointer]) return false;
Let’s say our string was “abcba” though. The letter “a” and letter “a” on the both ends are the same so it would pass the return false line area and go to the next line which will increment or decrement depending on what it is. If it is a left pointer it will move more to the right and vice versa so that the pointers can compare both sides of the string.
leftPointer++;
rightPointer — ;
}
Now once the pointers are at the same point in the middle, the program will break out of the while loop and will run into the return true statement because that would indicate it never made the if condition true where both sides aren’t the same. This would mean it is a palindrome.
return true
}
Final results for this solution look like this:
function isPalindrome(string) {
let leftPointer = 0
let rightPointer = string.length-1
while (leftPointer < rightPointer){
if(string[leftPointer] !== string[rightPointer]) return false;
leftPointer++;
rightPointer — ;
}
return true
}
At the end of it all, we are left with a time complexity of O(n) and a space complexity of O(1). Why does this approach have better time and space complexity? This is because it doesn’t have to create a new string, all the program has to do is use some simple pointers working with the same size of an input and ultimately return true or false which takes less time than the first solution.
The palindrome question does a great job testing developer’s basic understanding of how to manipulate a string. It is a problem simple enough to solve to have a clearer chance to understand the reasons behind the big-O notations given to each which developers can use in more complicated problems down the road. I hope that this shorter blog was simple enough to help you understand how to solve this question by ultimately breaking down the parts of each solution and give some insight into how big-O notations are given. Until next time!
Comments
Loading comments…