FB tag

Rearrange String k Distance Apart

先根据剩余的count来决定当前的StringBuffer可以append哪个character。然后用另一个维护一个队列，只有当queue的size大于等于k时，下一个曾经append过的character可以被加入maxHeap中，成为一个被加入StringBuffer里的candidate。

解法一：

public class Solution {
    public String rearrangeString(String str, int k) {
        if (str == null || str.length() == 0) {
            return "";
        }

        int[] count = new int[26];
        int[] valid = new int[26];

        for (char c: str.toCharArray()) {
            count[c - 'a']++;
        }

        int length = str.length();
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < length; i++) {
            int pos = helper(count, valid, i);
            if (pos == -1) return "";
            count[pos]--;
            sb.append((char) ('a' + pos));
            valid[pos] = i + k;
        }
        return sb.toString();
    }

    private int helper(int[] count, int[] valid, int index) {
        int pos = -1, max = Integer.MIN_VALUE;
        for (int i = 0; i < 26; i++) {
            if (count[i] > 0 && count[i] > max && index >= valid[i]) {
                max = count[i];
                pos = i;
            }
        }
        return pos;
    } 
}

解法二：

public class Solution {
    public String rearrangeString(String str, int k) {
        if (str == null || str.length() == 0) {
            return "";
        }

        Map<Character, Integer> map = new HashMap<Character, Integer>();
        for (char c: str.toCharArray()) {
            if (!map.containsKey(c)) {
                map.put(c, 1);
            } else {
                map.put(c, map.get(c) + 1);
            }
        }

        Queue<Tuple> maxHeap = new PriorityQueue<Tuple>(new Comparator<Tuple>(){
            public int compare(Tuple a, Tuple b) {
                return b.count - a.count;
            }
        });

        for (char c: map.keySet()) {
            int count = map.get(c);
            maxHeap.offer(new Tuple(c, count));
        }

        Queue<Tuple> queue = new LinkedList<Tuple>();
        StringBuffer sb = new StringBuffer();

        while (!maxHeap.isEmpty()) {
            Tuple t = maxHeap.poll();
            sb.append(t.c);
            t.count--;
            queue.offer(t);

            if (queue.size() < k) {
                continue;
            }

            Tuple t2 = queue.poll();
            if (t2.count > 0) {
                maxHeap.offer(t2);
            }
        }
        return sb.length() == str.length() ? sb.toString() : "";
    }
}

class Tuple {
    char c;
    int count;

    public Tuple(char c, int count) {
        this.c = c;
        this.count = count;
    }
}