CodeSignal Arcade – palindromeRearranging
Problem
Given a string, find out if its characters can be rearranged to form a palindrome.
Example
For inputString = "aabb", the output should besolution(inputString) = true.
We can rearrange "aabb" to make "abba", which is a palindrome.
Solution
Idea
Firstly, we need to understand palindrome. A palindrome phrase is a phrase that is spelt the same as forth and back. For example, “Step on no pets” is a palindrome phrase as it can spell the same back or forth.
Secondly, I think that this problem wants to teach us the rule to form a palindrome. If I can discover the pattern, I will solve it easily.
Let’s look at an example: abbcabb.
- There’re 2
a - There’re 4
b - There’s 1
c
This string can be re-arranged to a palindrome, such as abbcbba. Therefore, the pattern is quite simple:
- Each character should have even number of appearances.
- Only allow one exception of the previous rule.
Code
function solution(inputString) {
// turn string to array of characters
const chars = [...inputString];
let charsCount = {};
// count each character appearances in the array
for (let i = 0; i < chars.length; i++) {
const char = chars[i];
charsCount[char] === undefined ? charsCount[char] = 1 : charsCount[char] += 1;
}
let result = true;
let ignoreCount = 0;
Object.keys(charsCount).forEach(function(key) {
// in palindrome, each valid character should have even number of appearances
if (charsCount[key] % 2 === 0) {
return;
}
// when there's more than one exception, it's always invalid
if (ignoreCount > 0) {
result = false;
return;
}
// in palindrome, we can have only one exception
ignoreCount += 1;
});
return result;
}