JavaScript O(n) time and space


  • 0
    var rearrangeString = function(s, k) {
        if (s.length < 2 || !k) return s;
        const buckets = [];
        let a = 'a'.charCodeAt(0);
        for (let i = 0; i < s.length; i++) {
            let key = s.charCodeAt(i) - a;
            buckets[key] = (buckets[key] || 0) + 1;
        }
        let res = '';
        let added = { length: 0 };
        while (res.length < s.length) {
            let maxIndex = -1;
            for (let i = 0; i < buckets.length; i++) {
                if (buckets[i] && !added[i] && (maxIndex === -1 || buckets[i] > buckets[maxIndex])) {
                    maxIndex = i;
                }
            }
            if (maxIndex === -1) return '';
            res += String.fromCharCode(a + maxIndex);
            buckets[maxIndex]--;
            added[maxIndex] = 1;
            if (++added.length === k) added = { length: 0 };
        }
        return res;
    };
    

    For large or variable character sets we could use a max heap.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.