CodeSignal Arcade – palindromeRearranging

8 months ago

ngocnb

2 minutes

Contents

1 Problem
2 Solution
- 2.1 Idea
- 2.2 Code

Problem

Given a string, find out if its characters can be rearranged to form a palindrome.

Example

For inputString = "aabb", the output should be
solution(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;
}