---
# System prepended metadata

title: 0767. Reorganize String
tags: [Leetcode, Priority Queue, Task Scheduler, Medium, Greedy]

---

# 0767. Reorganize String
###### tags: `Leetcode` `Medium` `Priority Queue` `Greedy` `Task Scheduler`
Link: https://leetcode.com/problems/reorganize-string/
## 思路 $O(N)$ $O(1)$
和[0621. Task Scheduler](https://hackmd.io/9drzP_oOQ3SRFsKkaWyaLQ) 有一点点像
和[1054. Distant Barcodes](https://hackmd.io/5RbR4Q9pRBKgIMKYQjgxQg)很像
但差别在于如果没办法紧凑排列就不会让你排了
所以不需要用621的方法
只需要先找到出现最多的字母，然后把它们放在奇数位
然后遍历count array，对于每一个character，都填完再move on到下一个，填完奇数位再填偶数位
注意char array转成string 要用```String.valueOf(arr)```不能用```arr.toString()```
## Code
```java=
class Solution {
    public String reorganizeString(String s) {
        int[] count = new int[26];
        for(int i = 0;i < s.length();i++){
            count[s.charAt(i)-'a']++;
        }
        
        int maxIdx = 0;
        
        for(int i = 0;i < count.length;i++){
            if(count[i]>count[maxIdx]){
                maxIdx = i;
            }
        }
        if(count[maxIdx] > (s.length()+1)/2){
            return "";
        }
        
        char[] cs = new char[s.length()];
        int i = 0;
        while(count[maxIdx]-- > 0){
            cs[i] = (char)(maxIdx+'a');
            i+=2;
        }
        
        for(int j = 0;j < count.length;j++){
            while(count[j]-- > 0){
                if(i >= s.length()) i = 1;
                cs[i] = (char)(j+'a');
                i+=2;
            }
        }
        return String.valueOf(cs);
    }
}
```
