358 Rearrange String k Distance Apart

358. Rearrange String k Distance Apart

1. Question

Given a non-empty stringsand an integer k, rearrange the string such that the same characters are at least distance k from each other.

All input strings are given in lowercase letters. If it is not possible to rearrange the string, return an empty string"".

Example 1:

s = "aabbcc", k = 3

Result: "abcabc"

The same letters are at least distance 3 from each other.

Example 2:

s = "aaabc", k = 3 

Answer: ""

It is not possible to rearrange the string.

Example 3:

s = "aaadbbcc", k = 2

Answer: "abacabcd"

Another possible answer is: "abcabcda"

The same letters are at least distance 2 from each other.

2. Implementation

(1) Heap

class Solution {
    public String rearrangeString(String s, int k) {
        if (k <= 1) {
            return s;
        }

        int[] count = new int[256];
        for (char c : s.toCharArray()) {
            ++count[c];
        }

        PriorityQueue<CharInfo> maxHeap = new PriorityQueue<>();

        for (int i = 0; i < 256; i++) {
            if (count[i] != 0) {
                maxHeap.add(new CharInfo((char)i, count[i]));
            }
        }

        Queue<CharInfo> buffer = new LinkedList<>();
        StringBuilder res = new StringBuilder();

        while (!maxHeap.isEmpty()) {
            CharInfo curChar = maxHeap.remove();
            res.append(curChar.val);
            --curChar.freq;
            buffer.add(curChar);

            if (buffer.size() == k) {
                curChar = buffer.remove();
                if (curChar.freq > 0) {
                    maxHeap.add(curChar);
                }
            }
        }
        return res.length() == s.length() ? res.toString() : "";
    }

    class CharInfo implements Comparable<CharInfo> {
        char val;
        int freq;

        public CharInfo(char val, int freq) {
            this.val = val;
            this.freq = freq;
        }

        public int compareTo(CharInfo that) {
            return that.freq - this.freq;
        }
    }
}

3. Time & Space Complexity

Heap: 时间复杂度O(nlog26) => O(n), 在这题heap存储的元素为26，因为所有字符都是lowercase, 空间复杂度O(n)