Can a string have a palindrome, is there any better way to do this?

Question

I had a very interesting interview question today :

Given a string, you have to determine whether that string could have a palindrome when permuted.

The following is the implementation I came up with. But is there a better solution ?

function canBePalindrome(someStr) {

    if (typeof someStr !== "string") {
      throw new Error("Expecting argument to be a string !");
    }

    if (someStr.length == 1) return someStr;
    var canBePalin = false;
    var _chunks = someStr.split("");
    var _length = _chunks.length;
    for (var i = 0; i < _length; i++) {
      for (var j = i + 1; j < _length; j++) {
        var temp_char = _chunks[i];
        _chunks[i] = _chunks[j];
        _chunks[j] = temp_char;

        if (isPalindrome(_chunks.join(""))) return true;

      }
    }
    return canBePalin;

  } //End of canBePalindrome


function isPalindrome(someStr) {
    //console.log("Checking for:"+someStr);
    var original = someStr.split("");
    return someStr === original.reverse().join("");
  } //End of isPalindrome

canBePalindrome("mdadm");

This wouldn't be a possible duplicate because, i'm not checking if it is palindrome directly, but permuting and checking it.

Answer 1

Keep a map of characters, count them, and see if the count is even for all characters, if it is, a palindrome can be created

function canBePalindrome(someStr) {
    var map = {};
    var arr = someStr.split('');

    arr.forEach(function(s) {
        s in map ? map[s]++ : map[s] = 1;
    });

    var len = Object.keys(map).filter(function(o) {
        return map[o] % 2;
    }).length;

    return arr.length % 2 ? len === 1 : len === 0;
}

FIDDLE

A "golfed" version of the above would be

function canBePalindrome(someStr) {
    return (function(m, a, l) {
        a.forEach(function(s) { s in m ? m[s]++ : m[s] = 1 });  
        l = Object.keys(m).filter(function(o) { return m[o] % 2 }).length;
        return a.length % 2 ? l === 1 : l === 0;
    })({}, someStr.split(''));
}

Answer 2

If all the letters in a string have an even count, except for at most one, you can always reorganize them into a palindrome. My solution is a little longer than others because I tried to minimize performance overhead of loops with functions and unnecessary array creation.

aaaabbbb => aabbbbaa
aaaabbbbc => aabbcbbaa


function isPalindromable(str) {
    var map = getCharCount(str);
    var nonPairs = 0;
    for (var char in charMap) {
        if (charMap[char] % 2 != 0)
            nonPairs++;
        if (nonPairs > 1)
            return false;
    }
    return true;
}

function getCharCount(str) {
    // Number of times each string appeared
    var map = {};
    for (var i = 0; i < str.length; i++) {
        var ch = str.charAt(i);
        map[ch] = ++map[ch] || 1;
    }
    return map;
}

If you like one liners (not as fast, but kind of elegant)

function isPalindromable(str) {
    var charMap = getCharCountMap(str);
    return Object.keys(charMap).filter(char => charMap[char] %2 > 0).length <= 1;
}

function getCharCountMap(str) {
    return str.split('').reduce((prev, cur) => (prev[cur] = ++prev[cur] || 1, prev) , {})
}

Performance Edit

I benchmarked the three solutions. Mine was the slowest when the strings were short, and fastest for longer strings. However, a friend at work came up with a solution that ends up being fastest, maybe because it only has one loop but doesn't need to sort. http://jsperf.com/can-string-be-made-into-palindrome/2

function canBePalindromeReplace(string) {
    var oddCount = 0;

    while(string.length > 0) {
        var char = string.charAt(0);
        var stringLength = string.length;
        string = string.replace(new RegExp(char, 'g'), '');
        var diff = stringLength - string.length;
        if((diff % 2) != 0) {
            oddCount++;
            if(oddCount > 1) {
                return false;
            }
        }
    }

    return true;
}

Answer 3

Solution using sort and stack:

function canBePalindrome(someStr) {
    var stack = [];
    someStr.split('').sort().forEach(function(ch) {
        stack[stack.length - 1] === ch ? stack.pop() : stack.push(ch);
    });
    return stack.length < 2;
}