规定间隔内，重新排列字符串中的字符

给定一个字符串及一个最小间隔，重新排列字符串中的字符，使得重排后的任意相同字符的间距要大于或等于给定的最小距离，返回一个任意符合规定的字符串即可。

Example:

Given ("ABC", 1)  return "ABC";Given ("ABB", 2)  return "BAB";Given ("ABB", 3)  return null;

分析

这题可以用Greedy的方法解决，方法就是在规定最小距离内总是先排字符数量多的字符。

可以用一个max heap来维护字符及其数量，每次pop出数量最多的字符先排。过程中注意检测无法找到符合规定的排列。

复杂度

time: nlog(n), space: O(n)

代码

public class Solution {    class Pair {        char c;        int freq;        Pair(char c, int freq) {this.c = c;this.freq = freq;        }    }    public String minDistancePermutation(String s, int minDistance) {        if (minDistance <= 1)return s;        PriorityQueue<Pair> pq = new PriorityQueue<>(new Comparator<Pair>() {@Overridepublic int compare(Pair p1, Pair p2) {    if (p2.freq != p1.freq)        return p2.freq - p1.freq;    else        return p1.c - p2.c;}        });    // 根据字符的数量，依次push到queue中        Map<Character, Integer> map = new HashMap<>();        for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);if (!map.containsKey(c))    map.put(c, 1);else    map.put(c, map.get(c) + 1);        }         for (Map.Entry entry : map.entrySet()) {pq.add(new Pair((char)entry.getKey(), (int)entry.getValue()));        }StringBuilder sb = new StringBuilder();        while (!pq.isEmpty()) {// 发现无法找到满足要求的排序，返回nullif (pq.peek().freq > 1 && pq.size() < minDistance)    return null;List<Pair> temp = new ArrayList<>();// 最小距离内，每次先排数量多的字符for (int i = 0; i < minDistance && !pq.isEmpty(); i++) {    Pair pair = pq.remove();    sb.append(pair.c);    pair.freq--;    temp.add(pair);}// 对于没排完的字符，重新push到queue中参与排列for (Pair p : temp) {    if (p.freq > 0)        pq.add(p);}        }        return sb.toString();    }}