Check if string can be rearranged into a palindrome

I created a function to test whether a single word string can be a rearranged into a palindrome (doesn't have to be a real word). My logic was if the string has an even number of letters, then each letter must occur twice. If the string has an odd number of letters, each letter must occur twice except for one.

function checkPalindrome(str) {
    var letters = str.split(''),
        unique = [],
        match = {},
        single = [];

    var findUnique = function(arr, letter) {
        for (var k = 0; k < arr.length; k++) {
            if (arr[k].match(letter) && !unique.join('').match(letter)) {
                unique.push(arr[k]);
            }
        }
    }

    var sortLetters = function(arr, letter) {
        for (var i = 0; i < arr.length; i++) {
            if (arr[i] === letter) {
                if (match[letter] === undefined) {
                    match[letter] = 1;
                } else {
                    match[letter]++;
                }
            }
        }
    }

    for (var j = 0; j < letters.length; j++) {
        findUnique(letters, letters[j]);
    }

    for (var m = 0; m < unique.length; m++) {
        sortLetters(letters, unique[m]);
    }

    for (var key in match) {
        if (match[key] % 2 !== 0) {
            single.push(match[key])
        }
    }

    if (letters.length % 2 === 0) {
        if (single.length === 0) {
            return true;
        } else {
            return false;
        }
    } else {
        if (single.length === 1) {
            return true;
        } else {
            return false;
        }
    }
}

Any tips on how to improve this function in terms of efficiency ?

Your assumption is not quite correct.

• Even number of letters: every letter must occur even amount of times (not necessarily twice)

• Odd number letters: one letter must occur an odd amount of times, every other letter the same as above.

For example, aaa is a valid palindrome where no letter occurs once or twice.

As to your code, it is way too complex. If you look closely it has a complexity of \$O(n^2)\$, with n being the length of the string, because you have nested loops:
you call findUnique() which contains a loop over the letters in a loop over the letters.

You just have to count all the letters and check if there are letters with odd counts. If there are more than one letter with an odd counts the string does not satisfy the above palindrome condition. Furthermore, since a string with an even number letters must not have a letter with an odd count it is not necessary to check whether string length is even or not:

• even + odd = odd

• n * even = even

The function could look like this:

function canRearrangeToPalindrome(str)
{
    var letterCounts = {};
    var letter;
    var palindromeSum = 0;
    for (var i = 0; i < str.length; i++) {
        letter = str[i];
        letterCounts[letter] = letterCounts[letter] || 0;
        letterCounts[letter]++;
    }
    for (var letterCount in letterCounts) {
        palindromeSum += letterCounts[letterCount] % 2;
    }

    return palindromeSum < 2;
}

StackExchange Code Review Q#77511, answer score: 7