力扣 767. 重构字符串（每日一题）

给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。

若可行，输出任意可行的结果。若不可行，返回空字符串。

示例 1:

输入: S = “aab”
输出: “aba”
示例 2:

输入: S = “aaab”
输出: “”
注意:

S 只包含小写字母并且长度在[1, 500]区间内。

class Solution {
public:
    string reorganizeString(string S) {
             if(S.size()<2)
              return "";
              int l=S.size();
              int num[26]={0};
              for(int i=0;i<l;i++){
                   num[S[i]-'a']++;
              }
              int max=0;
              for(int i=0;i<26;i++){
                  if(num[i]>max){
                      max=num[i];
                  }
              }
              if(l%2==0){
              if(max>l/2)
                return "";}
            else{
                if(max>l/2+1)
                return "";
            }
               
            string s;
            while(1){
                int maxx=0;int la;
                for(int i=0;i<26;i++){
                    if(maxx<num[i]){
                         maxx=num[i];
                         la=i;
                    }
                }
                if(maxx==0)
                 break;
                s+=(la+'a');
                num[la]--;
                int max2=0;
                int lb;
                for(int i=0;i<26;i++){
                     if(i==la)
                     continue;;
                     if(max2<num[i]){
                        max2=num[i];
                        lb=i;
                     }
                }
                 if(max2==0)
                   continue;
                s+=(lb+'a');
                num[lb]--;
            }
            return s;
    }
};