4
\$\begingroup\$

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?

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.