Permutations of a string with duplicate characters

by Hari Menon

JavaScript

function getCharacterCountMap(s) {
    var map = {};
    for (var i = 0; i < s.length; i++) {
        var char = s.charAt(i);
        if (map[char] === undefined) {
            map[char] = 0;
        }
        map[char] = map[char] + 1;
    }
    return map;
}

function getPermutations(s) {
    var map = getCharacterCountMap(s);
    var result = [];
    populatePermutations(map, '', s.length, result);
    return result;
}

function populatePermutations(map, prefix, remaining, result) {
    if (remaining === 0) {
        result.push(prefix);
    }

    var keys = Object.keys(map);
    for (var i = 0; i < keys.length; i++) {
        var char = keys[i],
            count = map[char];
        if (count > 0) {
            map[char] = count - 1;
            populatePermutations(map, prefix + char, remaining - 1, result);
            map[char] = count;
        }
    }
}

console.log(getPermutations('112').join('\n'));