Palindrome Permutation

Day 49

Hey everyone, I hope you had an amazing weekend! Did you guys make some time for yourselves or did you do some extra work to help you later in the week?? Let me know! For today’s algorithm problem, I’m going to write a function that can return true or false if an inputted string can be permutated in any way to create a palindrome. Here’s an example:

Input: Tact Coa
Output: True (permutations: "taco cat", "atco cta", etc.)

In order to solve this problem, we have to actually think about what a palindrome looks like. Well, for starters it should have at least some pairs of letters. In the above example, there are two Ts, Cs, and As. Furthermore, there is only one letter that appears once, the O, which is the central part of each permutation. Keeping this in mind, wouldn’t it be cool to check how many times each character appears and then just see if it matches the above classifications of a palindrome?

I think a hash table would be the easiest to keep track, and at the end, if more than one variable has an odd count, the function would return false. Here’s what it looks like in code:

function isPermutation(str) {
    let foundOdd = false;
    let hasht = {};    
    for(let i = 0; i < str.length; i++) {
        hasht[str[i]] = 1;
        if (hasht[str[i]])
            hasht[str[i]] += 1;
        else 
            hash[str[i]] = 1
        if (hasht[str[i]] % 2 == 1){
            if (foundOdd)
                return false;
            foundOdd = true;
            }
        return true;
    }
}

Basically the code assigns a ternary variable which is turned to true when one odd count is found. For each iteration of the string array, I assign each index a key and a value starting at a count of 1. If that index already exists, the count variable increments, and if the count isn’t divisible by two, then the variable turns to true. In which case, if another count variable is odd, the function would return false as there can be no palindromes written from the original inputted string.

Anyways, if you guys learned something interesting or think the solution is pretty cool, click the clap button! If you have any better ways to solve it, feel free to leave a reply or contact me, thanks!