# Determine whether any permutation of a string is a palindrome

The task:

Given a string, determine whether any permutation of it is a palindrome.

For example, "carrace" should return true, since it can be rearranged to form "racecar", which is a palindrome. "daily" should return false, since there's no rearrangement that can form a palindrome.

My solution:

const isPalindrome = str => {
const letterOccurrences = str
.split("")
.reduce((acc, x) => {
acc[x] = acc[x] ? acc[x] + 1 : 1;
return acc;
}, {});

let numberOfOddOccurrences = 0;
const isMaxOneOddNumberLetter = x => x % 2 === 0 || ++numberOfOddOccurrences <= 1;
return Object.values(letterOccurrences).every(isMaxOneOddNumberLetter);
};

console.log(isPalindrome("carrace"));


Is it possible to write the function isMaxOneOddNumberLetter without mutation resp. side effects?

## 1 Answer

This is similar to a previous question of yours, Find the elements that appear only once, and the same advice applies: use a Set and maintain a flag instead of a count. If your Set ends up with size of zero or one, it's a palindrome. Otherwise no.

const isPalindrome = s => s.split("").reduce(
(once, x) => (once.delete(x) || once.add(x), once),
new Set()
).size <= 1


If inputs are constrained to 26 letters, you can map each letter to a unique power of 2 and replace the set with a bit vector (aka an "integer"), using XOR to track which bits appear an odd number of times. This may or may not be faster than a Set but it will certainly use less memory. I'll leave the implementation as an exercise for the reader.