Check if a string can be rearranged into a palindrome

This question has come up a few times during technical interviews, but revolves around a single algorithm that appears quite often throughout many algorithm problems — name hashmaps.

A hashmap is an object in Javascript that has a key and value pair that can be used to keep a running count of items.

The first thing you should be doing if you come across this problem is asking what a palindrome is defined in terms of letters. We all know that a palindrome can be read forward and backwards — popular examples being ‘racecar’ and ‘a man a plan a canal Panama’. In terms of character count, how would one define a palindrome?

A palindrome, in technical terms, an even count of characters (as they must be read forward or backwards) with at most one character appearing with an odd count.

aabb -> abba //True
aabbc -> abcba //True
aabbcc -> abccba //True
aaabbcc -> bcaaacb //True
aaabbb -> //False

Let’s look at each example in terms of character count.

aabb
2(a)
2(b)
= All even counts = True
aabbc
2 (a)
2 (b)
1 (c)
= All even counts with only 1 odd count = True
aabbcc
2 (a)
2 (b)
2 (c)
= All even counts = True
aaabbb
3 (a)
3 (b)
= More than 1 set of odd counts = False

Now that we have defined a palindrome in terms of what a computer can define, we can begin coding. First is building the hashmap.

function isPalindrome(str){
    let hashmap = {}
    for(let i = 0; i < str.length; i++){
        if(str[i] === " ") continue
        let char = str[i].toLowerCase()
        if(hashmap[str[i]]){
            hashmap[str[i]]++
        } else {
            hashmap[str[i]] = 1
        }
    }
    console.log(hashmap)
}

To build the hashmap, we first create an object and then iterate through the string. For every character, we check to see if the character is inside the hashmap yet. If it does not exist, then set it’s value to one to indicate that have seen the letter a single time. If it does exist, then we want to increment the value to say that the character has appeared again.

console.log(isPalindrome("is this a palindrome"))
{ i: 3,
  s: 2,
  t: 1,
  h: 1,
  a: 2,
  p: 1,
  l: 1,
  n: 1,
  d: 1,
  r: 1,
  o: 1,
  m: 1,
  e: 1 }
console.log(isPalindrome("racecar"))
{ r: 2, 
  a: 2, 
  c: 2, 
  e: 1 }
console.log(isPalindrome("A man a plan a canal Panama")
{ a: 10, 
  m: 2, 
  n: 4, 
  p: 2, 
  l: 2, 
  c: 1 }

I’ve copied the output for a few strings to see what each object looks like. Based on the initial definition of a palindrome, the first string does not qualify because it does not fit the criteria. The second and third strings do fit the criteria and would return true.

There are a few ways to proceed from here. One way is to filter out the even values of the object and if we have more than one value, it is not a palindrome.

The second option would be to rearrange our initial algorithm. An even appearance can be cancelled out. If we had the string ‘aa’, the object iterating would be: ‘a’ -> 1 and then ‘a’ -> 2. Instead of incrementing, we can decrement: {‘a’: 1} and then {‘a’: 0}.

function isPalindrome(str){
    let hashmap = {}
    for(let i = 0; i < str.length; i++){
        if(str[i] === " ") continue
        let char = str[i].toLowerCase()
        if(hashmap[str[i]]){
            hashmap[str[i]]-- //Updated from ++ to --
        } else {
            hashmap[str[i]] = 1
        }
    }
    let arr = []
    for(let char in hashmap)
        if(hashmap[char] > 0)
            arr.push(char)
    return arr.length === 1 || arr.length === 0
}