一道google的题目，至今没看到正确答案。

d=2的话就是隔一个吧？"aaaabbbcc" -> "ababacabc"，可以用贪心啊。

题目没有说清楚是at-least-d-distance还是exact-d-distance
后者的话答案是bababacac

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

请教exact如何做...

这是道FB题吧 当年面FB的时候做过。。贪心应该是可解的。。

1. public static String taskScheduler(String tasks, int n) {
   
2.                 StringBuilder sb = new StringBuilder();
   
3.                 HashMap<Character, Integer> countMap = new HashMap<Character, Integer>();
   
4.                 for(char c : tasks.toCharArray()) countMap.put(c, countMap.containsKey(c) ? countMap.get(c) + 1 : 1);
   
5.                 // sort the task by their occurence time (N/c * c *logk)
   
6.                 PriorityQueue<Map.Entry<Character, Integer>> queue = new PriorityQueue<>(new Comparator<Map.Entry<Character, Integer>>(){
   
7.                         public int compare(Map.Entry<Character,Integer> e1, Map.Entry<Character,Integer> e2) {
   
8.                                 return e2.getValue() - e1.getValue();
   
9.                         }
   
10.                 });
    
11. 
    
12.                 for(Map.Entry entry : countMap.entrySet()) queue.offer(entry);
    
13.                
    
14.                 while(!queue.isEmpty()) {
    
15.                         List<Map.Entry> refill = new ArrayList<Map.Entry>();
    
16.                         int i = 0;
    
17.                         for(i = 0; i < n && !queue.isEmpty(); i++) {
    
18.                                 Map.Entry e = queue.poll();
    
19.                                 sb.append(e.getKey());
    
20.                                 int count = (Integer)e.getValue();
    
21.                                 if(count > 1) refill.add(new AbstractMap.SimpleEntry<Character, Integer>((Character)e.getKey(), count - 1));
    
22.                         }
    
23.                         while(i++ < n && refill.size() > 0) sb.append("_");
    
24.                         // refill the task which hasn't finished yet
    
25.                         for(Map.Entry e : refill) queue.offer(e);
    
26.                 }
    
27.                 return sb.toString();
    
28.         }

复制代码

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

除了maxheap， 同事维护一个size = d-1的queue就行，(d如果等于2就相当于另外一道题，不能连续，这种情况其实可以不用queue，直接check一下Peek的character是不是等于last string position的就行）

直接用256大小数组表示string啊 每次找最大值也是O(1)的时间，其实对于所有有限的字母 字符串 直接开数组用下标计数会比hashmap或heap快很多。