# (FB) Rearrange String k Distance Apart

## (高频) Rearrange String k Distance Apart

### [Rearrange String k Distance Apart](https://leetcode.com/problems/rearrange-string-k-distance-apart/)

第一次写的时候，用的是自定义 tuple(char, count, timestamp) + heap 的贪心法，每次取 count 最大的元素，count 一样取 timestamp 最小的。

但是挂在了 "aaabc" k = 2，上，正解是 "abaca"。

#### 换句话说，条件允许的时候我们要从堆顶拿元素，但是堆顶元素非法的时候，不一定代表此时无解。

#### 因此我们需要在此基础上加一个 queue，来维护这次循环寻找元素时候的解；如果在任何时刻 maxHeap 里没东西了，但是 queue 里还有，都可以说明此时真的没有合法元素了，返回 "".

#### 速度尚可，超过 48%

```java
public class Solution {
    private class Tuple{
        char chr;
        int count;
        int timestamp;
        public Tuple(char chr, int count){
            this.chr = chr;
            this.count = count;
        }
    }

    private class TupleComparator implements Comparator<Tuple>{
        public int compare(Tuple a, Tuple b){
            if(a.count != b.count) return b.count - a.count;
            else return a.timestamp - b.timestamp;
        }
    }

    public String rearrangeString(String str, int k) {
        int[] hash = new int[26];
        PriorityQueue<Tuple> maxHeap = new PriorityQueue<Tuple>(new TupleComparator());
        for(int i = 0; i < str.length(); i++){
            hash[str.charAt(i) - 'a']++;
        }
        for(int i = 0; i < 26; i++){
            if(hash[i] > 0) maxHeap.offer(new Tuple((char)(i + 'a'),hash[i]));
        }

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

        int time = 0;

        while(!maxHeap.isEmpty()){
            Tuple tuple = maxHeap.poll();
            time ++;
            if(tuple.timestamp != 0 && time - tuple.timestamp < k){
                queue.offer(tuple);
                continue;
            }
            sb.append(tuple.chr);
            tuple.count --;
            tuple.timestamp = time;
            if(tuple.count != 0) maxHeap.offer(tuple);

            while(!queue.isEmpty()) maxHeap.offer(queue.poll());
        }


        return !queue.isEmpty() ? "": sb.toString();
    }
}
```

#### 思路来自 <https://discuss.leetcode.com/topic/48125/java_solution_in_12_ms-o-n-time-and-space>

## 注意，下面的代码和画图有 bug.

## "aabbccd"

## k = 3

## 返回了 abcacdb, c 冲突了，正解是 abcabcd

#### 改良版的写法建立在下图的逻辑上：

> * **我们在一个 size = str.length 的 char\[] 上维护 size = k 的 bin 若干个**
> * **对于每个 bin ，里面都放置着最多 k 个 distinct character;**
> * **每个 bin 里面元素的顺序存在一种 consistent ordering，即一定会严格按照我们定义的 Tuple 顺序由大到小填充。因此 bin 与 bin 之间一定不会违反 distance constraint;**
> * **同时我们的遍历顺序是顺序依次遍历每个 bin，避免类似 AAAABBBBCCCCDDDD ，k = 3 的时候，实际 bin size 应该是 4 ，无脑从头填充会出 bug 的问题。**

#### 这种写法适合不适合写自己填空格的 follow-up，有待研究。。至少 AAABBBCCCDDD 这种填充时候需要额外判断一下 “这个 space 到底是不是必要的” 这类问题。

![](/files/-MUt7cC_lIIpsyT1ftMs)

#### 12ms，超过 90.16%

```java
    private class Tuple implements Comparable<Tuple>{
        char chr;
        int freq;
        public Tuple(char chr, int freq){
            this.chr = chr;
            this.freq = freq;
        }
        public int compareTo(Tuple b){
            if(this.freq != b.freq) return b.freq - this.freq;
            else return this.chr - b.chr;
        }
    }


    public String rearrangeString(String str, int k) {
        if(k < 2) return str;

        Tuple[] count = new Tuple[26];

        for(int i = 0; i < str.length(); i++){
            char chr = str.charAt(i);
            int index = (int) chr - 'a';

            if(count[index] == null) count[index] = new Tuple(chr, 0);
            count[index].freq++;
        }

        ArrayList<Tuple> list = new ArrayList<>();
        for(int i = 0; i < 26; i++){
            if(count[i] != null) list.add(count[i]);
        }
        Collections.sort(list);

        char[] rst = new char[str.length()];
        int binIndex = 0;
        int ptr = 0;
        for(int index = 0; index < list.size(); index++){
            Tuple tuple = list.get(index);
            for(int i = 0; i < tuple.freq; i++){
                rst[ptr] = tuple.chr;
                if(ptr > 0 && rst[ptr] == rst[ptr - 1]) return "";

                ptr += k;
                if(ptr >= rst.length) ptr = ++ binIndex;
            }
        }

        return new String(rst);
    }
```

### (FB) 不改顺序的 cooldown 输出

第二轮，老外面试官，给一个String, 如AABACCDCD, 插入'*'使同一个字母间隔为k: 如果k=3: A - - - A B - - A C - - - C D - - C D, 一开始理解有误，认为是要先shuffle字母顺序然后插入'*'，花了不少时间，然后面试官提示字母顺序不变。

刚刚面完，欧洲小哥，发上来攒人品 Tasks: 1, 1, 2, 1

cooldown: 2

Output: 7 (order is 1 - - 1 2 - 1)

Tasks: 1, 2, 3, 1, 2, 3

(cooldown): 3

Output: 7 (order is 1 2 3 - 1 2 3)

Tasks: 1, 2, 3 ,4, 5, 6, 2, 4, 6, 1, 2, 4

(cooldown): 6

Output: 18 (1 2 3 4 5 6 - - 2 - 4 - 6 1 - 2 - 4)

```java
    public static String schedule(int[] tasks, int k){
        // Key : task number
        // Value : index of last appearance
        HashMap<Integer, Integer> map = new HashMap<>();
        StringBuilder sb = new StringBuilder();
        int timestamp = 0;

        for(int i = 0; i < tasks.length; i++){
            int task = tasks[i];
            if(!map.containsKey(task)){
                sb.append("" + task);
            } else {
                while(timestamp - map.get(task) <= k){
                    sb.append("_");
                    timestamp ++;
                }
                sb.append("" + task);
            }
            map.put(task, timestamp++);
        }

        return sb.toString();
    }

    public static void main(String[] args){
        int[] tasks1 = new int[]{1,2,3,1,2,3};
        int cooldown1 = 3;

        int[] tasks2 = new int[]{1, 2, 3 ,4, 5, 6, 2, 4, 6, 1, 2, 4};
        int cooldown2 = 6;

        int[] tasks3 = new int[]{1,2,3,1,2,3};
        int cooldown4 = 3;

        System.out.println(schedule(tasks2, cooldown2));
```

<http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=137479&extra=page%3D1%26filter%3Dsortid%26sortid%3D311&page=1>

给定任务AABCB, 冷却时间k（相同任务之间的最短距离时间），任务顺序不能变，问完成任务的总时间。

例子：AABCB, k = 3, A \_ \_ A B C \_ B, 时间为8.

解法：用hashtable保存上次的时间。

Followup1：如果k很小，怎么优化？ 解法：之前的hashtable的大小是unique task的大小，如果k很小，可以只维护k那么大的hashtable

Followup2: 如果可以改变任务的顺序，最短的任务时间是多少？ 例子：AABBC, K=2, AB\*ABC, 时间为6.

解法：根据每个任务出现的频率排序，优先处理频率高的。但是具体细节没有时间讨论。

### (FB) 变种：任务调度，生成“最优”的任务序列，可以用空格占位；

* **问题一：返回最优长度**
* **问题二：返回带空格的最优序列**
* **follow up：**[**https://instant.1point3acres.com/thread/167190**](https://instant.1point3acres.com/thread/167190) **在这个基础上，已知cooldown会很小，可以视作constant，task的type会很多，让我减少空间复杂度 (这个是 task 顺序已经给好不需要动的情况)**


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mnunknown.gitbook.io/algorithm-notes/gao_989129_rearrange_string_k_distance_apart.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.