Determine whether any permutation of a string is a palindrome

Question

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?

Answer 1

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.