用backtracing做超时了，代码如下：

class Solution {public:    string res="";        string reorganizeString(string s) {        vector
     
       visited(s.size(),false);        string tmp="";        dfs(s,tmp,visited);        return res;    }        void dfs(string s, string tmp, vector
      
        &visited){        if (tmp.size()==s.size()){            res = tmp;            return;        }        for (int i=0;i
      
     

 

本题可以用优先队列+Greedy做。

首先对计算每个字母出现个数，根据个数建立优先队列，个数多的在前。每次选取队列前两个字母，这样一定不会有重复字母在一块。建立优先队列的时候，如果某个字母的出现次数比 (s.size()+1)/2 还要大，说明不行，返回""。

优先队列每次push和pop都要log(A)，所以时间复杂度为O(nlogA)。A为字母个数

顺便复习一下优先队列排序的写法。

class Solution {public:    struct node{        int count;        char ch;        node(int cnt, char c):count(cnt),ch(c){};        bool operator < (const node &a) const{            if (count==a.count) return ch>a.ch;            return count
     
       count;        for (char ch:s) ++count[ch];        priority_queue
      
        q;        for (auto x:count){            if (x.second>(s.size()+1)/2) return "";            q.push(node(x.second,x.first));        }                string res="";        while (q.size()>=2){            node a=q.top(); q.pop();            node b=q.top(); q.pop();            res.push_back(a.ch);            res.push_back(b.ch);            if (--a.count>0) q.push(a);            if (--b.count>0) q.push(b);        }        if (q.size()==1) res+=q.top().ch;        return res;    }    };