Advanced Palindrome Interview Question JavaScript

Link to the video

365 days of coding day 1! If you don’t know what 365 days of coding is check this out! Today we are going to tackle a popular interview question is the palindrome test. These solutions are for palindromes with numbers, multiple words, spaces, and punctuation. For simple 1 word palindromes without numbers, spaces, or punctuation check out this post.

link to video of solutions: https://youtu.be/6-rf58ep7lk

Disclaimer: there are MANY ways to solve this problem these are a few answers that I would see or use in a coding interview and would accept as a proper answers

TLDR: explanation of best solutions at the bottom and actual solutions at the bottom of each section

The Problem

Create a function that accepts a string and returns if it is a palindrome.

Example:

      isPalindrome('Red rum, sir, is murder') //true
      isPalindrome('No lemon, no melon') //true
      isPalindrome('Eva, can I see bees in a cave?') //true
      isPalindrome('My dogs are adorable') //false
      isPalindrome('I come in peace!') //false
      isPalindrome("Racecar") //true
      isPalindrome("HelloDevWorld") //false
      isPalindrome("9119") //true
      isPalindrome("12345") //false

What is a Palindrome

Well knowing what a palindrome is may be a little important. A palindrome is a word, phrase, or sequence that reads the same backward as forward. Sentence-length palindromes ignore capitalization, punctuation, and word boundaries.

Solutions

what do we need to do?

• create a function that accepts something

• possible solution is to reverse the string and see if it is equal to the accepted string

  • check if the argument that was passed is a string

    • if it is

      • make it lowercase
      • strip our special characters and spaces
      • reverse it
      • check it against the passed input that is lowercase and is stripped of special characters and spaces

    • if not

      • make it into a string
      • reverse it
      • check it against passed input that also converted to a string

• possible solution check first and last letter for each index and see if they are the same (1 and last, 2 and second to last, etc)

  • check if the argument that was passed is a string

    • if it is

      • make it lowercase
      • strip out special characters and spaces
      • for each index of the string up until the middle character

      • check that character against the character in the same spot at the end of the string

        • first and last letter
        • second and second to last letter
        • if they are the same different return false and continue the loop

      • if the loop finishes return true

• return true if it is else return false

Solution 1 - Readability

first we need to create a function that accepts something

function isPalindrome(input) {
    //check if the argument that was passed is a string

    //if it is 
        //make it lowercase
        //strip out special characters and spaces
        //reverse it
        //check it against the passed input that is lowercase and is stripped of special characters and spaces
    //if not
        //make it into a string 
        //reverse it
        //check it against passed input that also converted to a string
}

we need to check if the argument that was passed is a string. If you don’t know about typeof please reference this MDN page

function isPalindrome(input) {
    if(typeof(input) === 'string') {

    //if it is 
        //make it lowercase
        //strip out special characters and spaces
        //reverse it
        //check it against the passed input that is lowercase and is stripped of special characters and spaces
    } else {
    //if not
        //make it into a string 
        //reverse it
        //check it against passed input that also converted to a string
    }
}

We now need to manipulate the string to make it lowercase, strip out the punctuation, and strip out the spaces. We make it lower case so that it doesn’t matter if they send in a capitalized letter in the string like in one of the test cases (“Racecar”) if we don’t do this “Racecar” will return as false since “racecaR” does not equal “Racecar”. We strip out the spaces and punctuation because the definition of a palindrome says we ignore capitalization, punctuation, and word boundaries. if you do not know about .toLowerCase(), .replace(), or regex check out each linked page on them before going further.

function isPalindrome(input) {
    if(typeof(input) === 'string') {
        input = input.toLowerCase().replace(/[^\w]|_/g, '');
        //reverse it
        //check it against the passed input that is lowercase and is stripped of special characters and spaces
    } else {
    //if not
        //make it into a string 
        //reverse it
        //check it against passed input that also converted to a string
    }
}

we then need to reverse that new string. if you don’t know what .split(), .join(), or .reverse() are check out each W3Schools page (linked on each one) before going further.

function isPalindrome(input) {
    if(typeof(input) === 'string') {
        input = input.toLowerCase().replace(/[^\w]|_/g, '');
        input.split('').reverse().join('');
        //check it against the passed input that is lowercase and is stripped of special characters and spaces
    } else {
    //if not
        //make it into a string 
        //reverse it
        //check it against passed input that also converted to a string
    }
}

now we just need to check it against the input that was passed

function isPalindrome(input) {
    if(typeof(input) === 'string') {
        input = input.toLowerCase().replace(/[^\w]|_/g, '');
        input.split('').reverse().join('');
        return input === input.split('').reverse().join('');
    } else {
    //if not
        //make it into a string 
        //reverse it
        //check it against passed input that also converted to a string
    }
}

if it is not a string it is much simpler. We do the same thing but we don’t need to sanitize the string since there is nothing to sanitize. so all we need to do it make it to a string, do the same thing as before to reverse it, and check it against the input that was passed like before.

function isPalindrome(input) {
  if(typeof(input) === 'string') {
    input = input.toLowerCase().replace(/[^\w]|_/g, '');
    return input === input.split('').reverse().join('');
  } else {
    return input.toString() === input.toString().split('').reverse().join('');
  }
}

if you want to “clean this up” (some may find this harder to read)/be fancy and make it a bit shorter you can also do this with ternaries if you don’t know what that is check out this MDN page

function isPalindrome(input) {
  return (typeof(input) === 'string') ?
    input.toLowerCase().replace(/[^\w]|_/g, '') === input.toLowerCase().replace(/[^\w]|_/g, '').split('').reverse().join('') 
  : input.toString() === input.toString().split('').reverse().join('')
}

Solution 2 - Performance

Now lets get a little more complicated and write out the solution for the second possible way of coming up with the solution, check first and last letter for each index and see if they are the same (1 and last, 2 and second to last, etc.)

This will be the most performant because we are only comparing up to the middle character and the string isn’t being manipulated other than the lower case. It also fails fast as it will return false quickly (potentially on the first character) if it isn’t the same rather than comparing the whole array to another array it only compares the characters its currently on.

The beginning is the same as last time create a function that accepts something

function isPalindrome(input){
    //if it is 
        //make it lowercase
        //strip out special characters and spaces
    //for each index of the string up until the middle character
        //check that character against the character in the same spot at the end of the string
    //if they are the same different return false and continue the loop
    //if the loop finishes return true
}

First we need to check if the passed value is a string and if it is make it lowercase and strip out the special characters. In case you skipped to this solution this is why (same explanation as solution 1) we make it lower case so that it doesn’t matter if they send in a capitalized letter in the string like in one of the test cases (“Racecar”) if we don’t do this “Racecar” will return as false since “racecaR” does not equal “Racecar”. We strip out the spaces and punctuation because the definition of a palindrome says we ignore capitalization, punctuation, and word boundaries. if you do not know about .toLowerCase(), .replace(), or regex check out each linked page on them before going further. If it is not a string we need to make it a string so that we can parse it as charAt() (which we will be using) is a string chained function

function isPalindrome(input){
  input = (typeof(input) === "string") ? input.toLowerCase().replace(/[^\w]|_/g, '') : input.toString()
    //for each index of the string up until the middle character
        //check that character against the character in the same spot at the end of the string
    //if they are the same different return false and continue the loop
    //if the loop finishes return true
}

For this loop we only need to loop until the middle character of the string instead of just the whole string since we are comparing the start to the end the whole time by the time we hit the middle we have compared all of the characters. If you don’t know Math.floor(), for loops, or .charAt() check out each W3Schools page (linked on each one) before going further.

we will be using Math.floor() to get the index of the middle character to stop at, for loop to loop through the string, and charAt() to check the character at each index

first we need to loop through the string until the middle character

function isPalindrome(input){
  input = (typeof(input) === "string") ? input.toLowerCase().replace(/[^\w]|_/g, '') : input.toString()
  for(let i = 0; i < Math.floor(input.length/2); i++){
      //check that character against the character in the same spot at the end of the string
      //if they are the same different return false and continue the loop
    //if the loop finishes return true
  }
}

now we need to check the character at the index and the opposite index as see if they are different. Return false if they are different and continue on the loop if they are the same.

We need check if they are not the same because if we check that they are equal and return true it will not complete the loop and you will get false positives. This will only break the loop if it fails and then will return true once we are sure they are the same (after the loop has completed) if they are not it will break the loop and return false.

function isPalindrome(input){
  input = (typeof(input) === "string") ? input.toLowerCase().replace(/[^\w]|_/g, '') : input.toString()
  for(let i = 0; i < Math.floor(input.length/2); i++){
    if(input.charAt(i) !== input.charAt(input.length-i-1)) return false
  }
  //if the loop finishes return true
}  

If the loop ends then we know they are all the same and we can return true.

function isPalindrome(input){
  input = (typeof(input) === "string") ? input.toLowerCase().replace(/[^\w]|_/g, '') : input.toString()
  for(let i = 0; i < Math.floor(input.length/2); i++){
    if(input.charAt(i) !== input.charAt(input.length-i-1)) return false
  }
  return true
}  

Conclusion

So which one is the best? I think both answers are just fine. I would never expect a junior developer to come in with solution 2. If they did and were able to explain why it was more performant I would be very impressed. If I were to write it I would write solution 1 this is because I would prefer readability over performance especially on a function that takes up such little processing power. However, if you were asked for the most efficient way especially if they have a large palindrome then solution 2 would be your best bet. In case you were interested here are the metrics for both solutions run by jsbench the tests that were run is the list in the examples.

Please leave your solutions that you came up with in the comments section. If you have any challenge you would like to see done also leave that in the comments below you may see it come up!

Comments

[𒎏Wii 🏳️‍⚧️]

Here's a simple solution in Lua:

local function palindrome(input)
  input = input:lower():gsub("[^a-z0-9]", "")
  return input:find(input:sub(1, math.floor(#input/2)):reverse().."$")
end