What's a Palindrome!?!?

#javascript #algorithms

Technical coding interviews or code challenges on websites like LeetCode, CodeWars or HackerRank can often include varying questions that revolve around a singular idea. For example, a palindrome can be the foundation of a multitude of different problems that can have varying requirements for solving the problem based on the specific question. In the event, you're presented with a problem that revolves around palindromes it would be beneficial to know what a palindrome is in the first place. Let's dive into what exactly makes a palindrome and a couple of problems that are centered around them.

A palindrome can be a word, number, phrase, or sequence of varying characters that reads the same forwards as it does backwards.

A palindrome can be made out of a string of characters provided that all characters in the string occur an equal number of times. Or, all characters in the string occur an equal number of times except for one character that occurs an odd number of times.

Examples:

noon is a valid palindrome

racecar is a valid palindrome

racecars is not a valid palindrome

In the first example above all characters occur an even number of times. In the second example, all characters occur an even number of times except for 'e' that occurs only once(an odd frequency). In the third invalid example, we have two occurrences of a character that occurs an odd number of times making it impossible to create a palindrome out of that string of characters.

Now let's solve a few problems that are centered around palindromes.

1. Given a string of lowercase characters [a-z] determine if it is a palindrome. For simplicity we are not going to worry about any edge cases in this problem

const isPalindrome = (str) => {
    const reversedString = str.split('').reverse().join('')
    return str === reversedString
}

isPalindrome("racecar")
=> true

isPalindrome("racecars")
=> false

Pretty simple right, we just use a few built-in functions to reverse the string and then return the value of a strict comparison between the original and the reversed string.

However, we need to always be aware of the performance implications of our code. Let's solve that again without the use of any built-in functions...

const isPalindrome = (str) => {
    for (let i = 0; i < str.length / 2; i++) {
       if (str[i] != str[str.length - (i + 1)]) return false
       // loops through characters on the front half 
       // of string and compares against the opposing 
       // character on the back half of the string
    }
    return true
}

isPalindrome("racecar")
=> true

isPalindrome("racecars")
=> false

I benchmarked the performance of the two above solutions using the string "racecar" on JSbench. That tool stated that the first solution was 89.56% slower than the second solution. Sometimes less code is actually slower code.

2. Given a string of lowercase characters [a-z] determine if a palindrome can be created from all the given characters. For simplicity we are not going to worry about any edge cases in this problem

const isPalindromePossible = (str) => {
   const frequencyCounter = {}
   for (let c of str) {
     frequencyCounter[c] = (frequencyCounter[c] || 0) + 1
   }

   let charsWithOddFrequency = 0 
   for (let c in frequencyCounter) {
     if (frequencyCounter[c] % 2 !== 0) charsWithOddFrequency += 1
   }
   return charsWithOddFrequency <= 1
}

isPalindromePossible("acerrac") //can be rearranged into 'racecar'
=> true

isPalindromePossible("acerracs") //cannot be rearranged into a palindrome, more than one character with odd frequency count
=> false

In the above solution, I created a frequency counter to keep track of the numerical occurrences of each character in the string using the for/of loop. In the for/in loop we are checking for odd occurrences of each character in the string, if we have more than one character with an odd frequency count we cannot create a palindrome out of the given characters.

I hope this helped you understand what a palindrome is and the restrictions around how you can create one. If you have any questions or any other fun problems revolving around palindromes drop them in the comments below.

Cheers!