Palindromes: Multiple Challenges, Strategies, and Solutions

Palindrome code challenges come in a variety of different flavors. Here are a few, roughly arranged from easier to more difficult, with multiple strategies and solutions.

1. Is it a Palindrome?

The basic challenge is to take in a string and figure out if the string is a palindrome or not.

In other words, this question is asking "If the string is reversed, would it be the same as the original string?". This leads to planning. We will need to reverse the string, and then compare the original string to the reversed string. If they are equal, then we should return true ("yes, it is a palindrome"), and if they are not equal, we should return false ("no, it is not a palindrome").

Possible Strategies

STRATEGY A: REVERSE AND COMPARE
One solution is to use the reverse method to reverse the characters in the string. This involves splitting the string into an array, reversing the order of the characters, and then re-joining the characters back into a string:

const reversed = string.split('').reverse().join('')

Next, compare the original string to the reversed string, and return true or false:

return reversed === string ? true : false

As a complete function, this might look like:

function palindrome(string) {
    const reversed = string.split('').reverse().join('')
    return reversed === string ? true : false
}

palindrome("dog") //false
palindrome("racecar") //true

STRATEGY B: COMPARE PAIRS OF OPPOSITE CHARACTERS
In this strategy, we compare the first and last character for equality using the every function, and then compare the second character to the second-to-last character, and so on. If we have all matches, we have a palindrome.

function palindrome(string) {
    return string.split('').every((character, index) => {
        return character === string[string.length - index - 1]
    })
}

In the first line inside the function, the string is split into an array, and the every() method is called on the array. It takes in two arguments, the character and the index number of that character. As it iterates through the array, it makes a comparison between pairs of characters at either end of the array.

Take the string "racecar", for example:

• The first time through, it compares the character at index 0 ("r") with the character at index 6 ("r")
  • string.length - index - 1 is equal to 7 - 0 - 1 is equal to 6
  • "r" === "r" //true
• The second time through, it compares the character at index 1 ("a") with the character at index 5 ("a")
  • string.length - index - 1 is equal to 7 - 1 - 1 is equal to 5
• This pattern continues until the end of the string, for as long as true is returned at each iteration. As soon as false is returned, the iteration stops and false is returned ("no, it is not a palindrome").

STRATEGY C: WITHOUT USING ANY HELPER METHODS
The solutions above are straightforward and concise, but relatively expensive on the processing side since they rely heavily on helper methods. We can reduce this expense by using for loops.

First, set up placeholder variables for an empty array:

let array = []

and an empty string

let reversedString = ""

In the first loop, we can move each character from the string into an array (without relying on the split() helper method).

    for (let i = 0; i < string.length; i++) {
        array.push(string[i])
    }

If our input was the string string = "racecar" our output would be:

array = ["r", "a", "c", "e", "c", "a", "r"]

In the next loop, we will use pop() to remove the last element of the array and add it onto the reversed string that we are building.

    for (let i = 0; i < array.length; i++) {
        reversedString += array.pop()
    }

If our input was the array array = ["r", "a", "c", "e", "c", "a", "r"], our output would be:

reversedString = "racecar"

Finally, we can compare the contents of the original string with the reversed string:

return string === reversedString ? true : false

When we compare string = "racecar" and reversedString = "racecar", we would find that they are deeply equal, and we would return true ("yes, it is a palindrome").

All together, we can write this as the function:

function palindrome(string) {
    let array = []
    let reversedString = ''

    for (let i = 0; i < string.length; i++) {
        array.push(string[i])
    }

    for (let i = 0; i < array.length; i++) {
        reversedString += array.pop()
    }

    return string === reversedString ? true : false 
}

STRATEGY D: COMPARING CHARACTERS FROM OUTSIDE IN WITHOUT HELPER METHODS
This strategy takes the logic from Strategy 2 (comparing characters from the outside in) but does it with a for loop instead of relying on the every() helper method. It also defines a variable let len = str.length / 2 in order to avoid repeats of the comparison once we hit the midpoint of the string. This increases the efficiency of the solution.

function palindrome(str) {
    let len = str.length;

    for (let i = 0; i < len/2; i++) {
        if (str[i] !== str[len - i - 1]) {
        return false;
        }
    }
    return true;
}

2. Palindrome Checking with Non-Standard Strings

The four strategies above can be used for other variations on the basic challenge, as well as on more complex palindrome problems.

For example, some challenges (such as FreeCodeCamp's Palindrome Checker) include more complex strings that may include punctuation, uppercase and lowercase letters, and symbols.

Possible Strategy

You can use the same strategies as above, but use regex or a similar strategy to parse the string and remove/correct the unwanted characters.

First, we can set a regex variable that includes our cleanup directions.

let regex = /[^A-Za-z0-9]/g

Then, we can use that regex expression to clean up the string before moving into our for loop.

str = str.toLowerCase().replace(regex, '')

Put it all together, and we have this function:

function palindrome(string) {
    let regex = /[^A-Za-z0-9]/g;
    str = string.toLowerCase().replace(regex, '');
    let len = string.length;

    for (var i = 0; i < len/2; i++) {
        if (string[i] !== string[len - i - 1]) {
        return false;
        }
    }
    return true;
}

3. Is it a permutation of a palindrome?

CodeAcademy's Palindrome Detector Challenge is a slightly different twist on the Palindrome Challenge. In this one, we need to figure out if ANY rearrangement of the characters in the string could form a palindrome. Therefore, in solving this challenge, we really don't care what order the characters are in, we just need to figure out a simple rule that we could use to distinguish between potential palindromes and non-palindromes.

Possible Strategy

In order to be a permutation of a palindrome, a string needs to have characters that can be matched in pairs. Here are some examples and non-examples:

• "racecar" is a palindrome, and has 2-r, 2-a, 2-c, and 1-e
• "toot" is a palindrome, and has 2-t, and 2-o
• "plant" is not a palindrome, as it has 1 of each individual letter

After brainstorming some examples, we can propose a rule: A palindrome must have matched pairs of letters (or, there must be an even number of each instance of a letter), AND there can be no more than one instance of a letter with an odd number of instances.

In order to code this, we need to be able to count the number of instances of each individual character in the string. First, we can set up some variables we'll be using:

let counts = {}
let odds = []

We will then be able to store the number of instances of each letter in the counts object, and store the letters that have an odd number of instances in the odds array.

Next, we can set up a loop to go through each character in the string and keep track of how many matches it has in the rest of the string. We can use the ternary operator at each index to ask (in pseudo-code):

• Does the counts object have a key of this letter yet?
• If yes, add 1 to that letter's count
• If no, set a key of that letter, and give that key a value of 1

for (let i = 0; i < string.length; i++) {
  counts[string[i]] ? counts[string[i]] = counts[string[i]] + 1 : counts[string[i]] = 1
}

Using the string "racecar" as an example, we would end up with a counts object that looks like counts = { r: 2, a: 2, c: 2, e: 1 }.

Next, we can iterate through the counts object to check how many keys have an odd value to determine whether the string is a palindrome. This iteration below will push any value that is odd into the odds array.

Object.values(counts).map(count => {
  if (count % 2 !== 0) {
    odds.push(count)
  }
})

Finally, we can just check the length of the odds array to determine if the original string could be rearranged to form a palindrome. If there is more than one element in the array, it cannot be a palindrome, and it would return false.

return odds.length > 1 ? false : true

Put it all together, and my solution looks like this:

function isPermPalindrome(string) {
    let counts = {}
    let odds = []
    for (let i = 0; i < string.length; i++) {
        counts[string[i]] ? counts[string[i]] = counts[string[i]] + 1 : counts[string[i]] = 1
    }

    Object.values(counts).map(count => {
        if (count % 2 !== 0) {
            odds.push(count)
        }
    })

    return odds.length > 1 ?  false : true
}

There are other solutions and further challenges on CodeAcademy's Palindrome Detector Challenge page.

4. Palindromes in Sub-Strings?

LeetCode's Longest Palindromic Sub-String is definitely a jump up in complexity compared to the others above. In this challenge, given a string of up to 1000 characters in length, you need to figure out the longest palindrome that exists within the string. The challenge includes tests, and you can try it out in multiple programming languages, and then compare your strategies and solutions with others.

What other palindrome challenges have you seen? How do you approach them?