Given an input string, determine whether the string could possibly be a palindrome if rearranged. It is not necessary to return the potential palindrome, just to identify whether one is possible.

Examples:

aabb  => true
abc   => false
aab   => true
ciicv => true
aba   => true
abac  => false


A palindrome can have any amount of pairs of letters, and optionally one single odd letter with no partner in the middle.

So, we can count the occurrences of each letter. If all counts are even, it is palindrome-able, as all letters have a partner to pair with, e.g.

aabb   => abba
aabbcc => abccba
012012 => 012210


We can also permit one single odd letter in any quantity, as it can appear in the middle of the potential palindrome, e.g.

aabbc     => abcba
aabbccc   => abcccba
333012012 => 012333210


That gives us an O(mn) approach, with m being the number of unique characters in the string.

function palindromeAble(input) {
const charCounts = {}
for (let char of input) {
charCounts[char] = charCounts[char] ? charCounts[char] + 1 : 1
}
let seenOdd = false
for (let char in charCounts) {
if (charCounts[char] % 2 !== 0) {
if (seenOdd) {
return false
}
seenOdd = true
}
}
return true
}

describe("palindromeAble", () => {
test.each([
["aabb", true],
["aab", true],
["ciicv", true],
["aba", true],
["abac", false],
])
(
"identifies possible palindrome",
(input, expectedPalindromeAble) => {
expect(palindromeAble(input)).toBe(expectedPalindromeAble)
}
)
})