题解
通常直接思考最佳策略是十分困难的，我们不妨思考每一种情况需要如何处理：
-
整个字符串只有一种字符
若字符串长度为 \(1\)，那么字符串本身即为答案；
若字符串长度大于等于 \(2\)，那么不存在可行方案 -
整个字符串只有两种字符 \(c_1，c_2\)，数量分别为 \(n_1，n_2\)
若字符 \(c_1\) 的数量 \(n_1\) == 字符 \(c_2\) 的数量 \(n_2\)，明显字符 \(c_1\) 和字符 \(c_2\) 交替出现即可
若字符 \(c_1\) 的数量 \(n_1\) > 字符 \(c_2\) 的数量 \(n_2\)，那么每两个字符 \(c_1\) 之间必须插入一个字符 \(c_2\)，也就是 \(n_1 - 1 \leq n_2\)。进一步思考，\(abs(n_1-n_2)\) 可以大于 \(1\) 吗？答案是不行，因为无法为每两个字符 \(c_1\) 之间插入一个字符 \(c_2\)
若字符 \(c_1\) 的数量 \(n_1\) < 字符 \(c_2\) 的数量 \(n_2\)，情况类似于 \(n_1 > n_2\) 的情况
从只有两种字符的情况，易得到启发：出现次数最多的字符，每两个之间必须插入至少一个不同的字符 -
整个字符串有 \(n(1 \leq n \leq 26)\) 种字符，第 \(i\) 种字符的数量为 \(n_i\)
由只有两种字符的字符串重构成功的方案来看，在有 \(n\) 种类字符的字符串中，需要首先处理出现次数最多的元素，不妨记出现次数为 \(m = max(n_i)\)
如下图所示，至少需要在 \(m\) 个元素之间插入一个与左右相邻元素均不同的元素：
所以，只需要将 \(m\) 个出现次数最多的元素（若有多个出现次数最多的元素，任意选择其中一个即可）先依次放入位置 \(x_j(1 \leq j \leq m)\)，随后将剩下的全部元素，按种类依次从位置 \(x_1\) 填到为止 \(x_m\)即可。
若 全部元素个数 - \(m < m - 1\)，则无解，否则有解。
问：为什么维护出现次数最多的种类元素是可行的方案？
答：因为题目要求的是相邻两个元素不可相同，那么在字符串中全部种类的单种元素的出现次数都不会超过\(max(n_i)\)。因此，只需要先维护其中一个出现次数最多的元素，并将剩余的元素按种类依次填入这\(max(n_i)\)个元素之后，必定符合每两个相邻元素不同的要求。按种类填入指的是，按单种元素
参考代码
class Solution {
public:
string reorganizeString(string s) {
string ans;
vector<int> mp(26);
for (auto &it: s) {
mp[it - 'a'] ++;
}
int mx = 0, idx = 0, sum = 0;
for (int i = 0; i < 26; ++ i) {
if (mx < mp[i]) {
mx = mp[i];
idx = i;
}
sum += mp[i];
}
if (sum - mx >= mx - 1) {
vector<vector<char>> v(mx);
for (auto &it: v) {
it.push_back('a' + idx);
}
mp[idx] = 0;
int cur = 0;
for (int i = 0; i < 26; ++ i) {
while (mp[i] > 0) {
v[cur].emplace_back('a' + i);
cur = (cur + 1) % mx;
-- mp[i];
}
}
for (auto &u: v) {
for (auto &i: u) {
ans.push_back(i);
}
}
}
return ans;
}
};