Permutations of a string with duplicate characters

by Hari Menon

HTML

<pre id="output"></pre>

JavaScript

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

function getPermutationsRecursive(map, prefix, remaining, result) {
    // Base Case - permutations has been completed
    if (remaining === 0) {
        result.push(prefix);
    }

    // Try remaining letters for next char, and generate remaining permutations
    console.log(map, remaining);
    var keys = Object.keys(map);
    for (var i = 0, len = keys.length; i < len; i++) {
        var char = keys[i],
            count = map[char];
        if (count > 0) {
            map[char] = count - 1;
            getPermutationsRecursive(map, prefix + char, remaining - 1, result);
            map[char] = count;
    		console.log('>>> ', map, remaining, count);
        }
    }
}

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

document.querySelector('#output').innerHTML = getPermutations('aaab').join('\n');