What’s a Palindrome!

What’s a Palindrome!:

 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 twooccurrences 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
Enter fullscreen mode Exit fullscreen mode

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  true

isPalindrome("racecars")
=> false
Enter fullscreen mode Exit fullscreen mode

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  true

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

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!

from Tumblr https://generouspiratequeen.tumblr.com/post/634294290630262784

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s