###### tags: `Leetcode` `medium` `hash` `string` `greedy` `counting` `heap` `python` `c++`

# 767. Reorganize String

## [題目連結:] https://leetcode.com/problems/reorganize-string/

## 題目:
Given a string ```s```, rearrange the characters of ```s``` so that any two adjacent characters are not the same.

Return any possible rearrangement of ```s``` or return ```""``` if not possible.

**Example 1:**

Input: s = "aab"
Output: "aba"

**Example 2:**

Input: s = "aaab"
Output: ""

## 解題想法:
* 此題為給一字串，求重構此字串，規則為相同的字符不可相鄰
* 若無法做到，回傳空字串
* 想法: greedy思考，每次優先用最多數量的char填入
* 初始需要工具:
* Python使用Counter紀錄數量: dic=Counter(s)
* res="#" : 紀錄最終結果，因為每次都要判斷res的最尾字符是否重複，避免一開始為空的情況，所以先加一個"#"
* while dic: 進行判斷
* 設布林值: **stop**=True
* stop判斷是否還有機會填字進入res
* 否則若某字太多一黨獨大，則根本沒機會了，會導致無限迴圈，所以若最後stop仍為True，則break跳出while
* 遍歷dic:
* 可用Counter中的函式**most_common()** [https://docs.python.org/zh-tw/3/library/collections.html#collections.Counter]
* for char, times in dic.most_common():
* **每次判斷res最後一個字是否與當前char重複**
* 若不重複，則將該char加入res，並將dic中該char的數量-1，且**將stop=False**，**then break**
* 若重複，則continue換下一個char試試
* 最後跑完for迴圈，判斷stop是否為True
* 若為True表示某字太多了，強制跳出迴圈

## Python:

from collections import Counter
class Solution(object):
    def reorganizeString(self, s):
        """
        :type s: str
        :rtype: str
        """
        #每次用最多數量的char填
        dic=Counter(s)
        res="#"
        while dic:
            #stop判斷是否還有機會填字進入res
            #否則若某字太多一黨獨大 根本沒機會了會無限迴圈
            stop=True 
            #技巧函式Counter的
            for char,times in dic.most_common():
                #每次判斷res最後一個字是否重複
                if res[-1]!=char:
                    res+=char
                    dic[char]-=1
                    #若已經為0 要整個刪掉以免幽靈人口
                    if dic[char]==0:
                        del dic[char]
                    stop=False
                    break
            if stop==True:
                break
        return res[1:] if len(res[1:])==len(s) else ""
    
result=Solution()
ans=result.reorganizeString(s = "aab")
print(ans)

## C++:
* C++沒有Counter，所以可以用**unordered_map**+**priority_queue**
* 注意，額外多一個flag，因為每輪que最多一個字加入res，其他都字都須加入到下一層que進行判斷

class Solution {
public:
    string reorganizeString(string s) {
        int n=s.size();
        string res="#";
        unordered_map<char, int> dic;
        for (char val: s) dic[val]+=1;
        priority_queue<pair<int, char>> que;
        //first: key; second:value
        for (auto& item: dic) que.push({item.second, item.first});
        //rearrange
        while (!que.empty()){
            bool stop=true;
            bool flag=true;
            int n=que.size();
            //Save the next layer
            priority_queue<pair<int, char>> nextQue;
            for (int i=0; i<n; i++){
                auto curPair= que.top(); que.pop();
                //Check whether the current character is repeated at the end of res
                if (res.back()!=curPair.second && flag==true){
                    res.push_back(curPair.second);
                    curPair.first-=1;
                    if (curPair.first>0) nextQue.push({curPair.first, curPair.second});
                    stop=false;
                    flag=false;
                }
                else
                    nextQue.push({curPair.first, curPair.second});
            }
            que=nextQue;
            if (stop==true) break;
        }
        return (res.substr(1).size()==n)? res.substr(1) : "";
    }
};