LeetCode 767. 重构字符串
给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。
若可行，输出任意可行的结果。若不可行，返回空字符串。
示例 1:
输入: S = “aab”
输出: “aba”
示例 2:
输入: S = “aaab”
输出: “”
注意:
S 只包含小写字母并且长度在[1, 500]区间内。
来源：力扣（LeetCode）
链接：//leetcode-cn.com/problems/reorganize-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
对字符串进行统计每一个字符出现的次数。
第一部分：先判断能否重新排布，当一个字母出现的个数比字符串长度一半还要多时就无法重新排布；
第二部分：进行重新排列，最长为500个，其实就可以开辟一个数组（相当于挖好坑，等下把萝卜埋下去就可以了），把同一字符间隔排序就好了：
1、以字符出现的个数多少来决定先排布哪个字符，举个栗子：aaaiij,如果不先排a，先把i和j用了，iji，就还剩下两个a，就无法重新排布。
2、先排0、2、4、6、8…位置上的，当已经填满一半时就可以排1、3、5、7…
举个栗子：aaaabbbbcccc
先排第一趟0、2、4、6、8、10：a_a_a_a_b_b_
接下来从1、3、5、7、9：ababacacbcbc
就完成了字符串的重新排列。
class Solution {
public:
string reorganizeString(string S) {
int num[30],l,p1,p2,temp[505],k,flag;
string res="";
fill(num,num+30,0);
for (int i=0;i<S.length();i++){
num[S[i]-'a']++;//对每一个字符进行统计出现的个数
}
for (int i=0;i<26;i++){
if (num[i]>=(S.length()+1)/2+1){//当有字符出现次数大于一般就判定为无法重新排列
return "";
}
}
l=0;//代表已完成重新排列的字符个数
p1 = -1;//记录当前填入的字符（找到的出现的次数的字符）
k=0;//当前填入到临时数组的下标
flag=0;//用与代表还没开始第二趟
while(l<S.length()){
if (l>=((S.length()+1)/2)&&flag==0){//当已填完一般的字符时，开始第二趟
k=1;
flag=1;
}
if (p1==-1||num[p1]==0){//当前指向的字符已全部完成了重新排列，需要找寻下一个字符
for (int i=0;i<26;i++){
if (num[i]!=0){
p1=i;
break;
}
}
for (int i=0;i<26;i++){//找到出现次数最多的字符
if (num[i]>num[p1]){
p1 = i;
}
}
}
temp[k]=p1;//填入该字符到临时数组中去
k+=2;//间隔填入
l++;
num[p1]--;
}
for (int i=0;i<S.length();i++){//按数组的排列，重新获得字符串
res+=('a'+temp[i]);
}
return res;
}
};
