描述
给定一个只包含小写字母’a’-‘z’的字符串 S ，你需要将 S 中的字符重新排序，使得任意两个相同的字符不连在一起。
如果有多个重排后字符串满足条件，输出字典序最小的一个。
输入
字符串S。(1 ≤ |S| ≤ 100000)
输出
输出字典序最小的答案或者INVALID。
样例输入
aaabc
样例输出
abaca
思路
绞尽脑汁过后，写了一个代码，自认为可解，然而提交后果断WA，后来仔细想了想，就是解不出来，放弃了。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57#include <bits/stdc++.h>
using namespace std;
int main()
{
char S[100005];
cin >> S;
int len = strlen(S);
map<char, int> HASH;
set<char> str;
int maxn = -2;
char ch;
for(int i = 0; i < len; i++) {
HASH[S[i]] += 1;
str.insert(S[i]);
if(HASH[S[i]] > maxn) {
maxn = HASH[S[i]];
ch = S[i];
}
}
if(maxn > (len + 1) / 2) {
cout << "INVALLD";
return 0;
}
if(maxn == (len + 1) / 2 && maxn > len / 2) {
str.erase(ch);
int LEN = str.size();
for(int i = 0; i < LEN; i++) {
cout << ch;
char c = *str.begin();
while(HASH[c]) {
cout << c << ch;
HASH[c] -= 1;
}
str.erase(c);
}
return 0;
}
int LEN = str.size();
for(int i = 0; i < LEN; i++) {
char c = *str.begin();
while(HASH[c]) {
cout << c;
HASH[c] -= 1;
for(int j = i + 1; j < str.size(); j++) {
char cc = *str.begin() + j;
if(HASH[cc]) {
cout << cc;
HASH[cc] -= 1;
break;
}
}
}
str.erase(c);
}
return 0;
}
看了官方题解，醍醐灌顶，暴力是最简单的解法。
《分隔相同字符》题目分析
首先我们需要分析INVALID的充分必要条件。容易看出充要条件是S中某个字符的数目超过了(|S|+1)/2。
换句话说，除非有一个字母数量 过多，否则一定可以有一个合法的重排方案。
例如样例”aaabc”，5个字符中有3个’a’。这个例子’a’的数量就在临界值上，我们必须在第1、3、5个位置上都放’a’才能把所有的’a’分隔开。如果’a’的数量再多1个，比如”aaaabc”，那就没办法把’a’都分隔开了，结果就是INVALID。
那么，当我们知道目前的S不是INVALID时，我们怎么求字典序最小的重排方案呢？ 这里我们可以使用一个贪心策略：我们按照’a’-‘z’的顺序枚举第一个字符c，如果除去c之后，S的剩余的字符仍然>不是INVALID，那么我们就把第一个字符定为c。之后我们可以用同样的策略确定第二位、第三位……，只是在确定第二位、第三位……的时候还需要要求当前字符不能与之前定下来的字符相同。
举个例子，假设S=”bbbac”，我们知道出现最多的’b’一共出现了3次，没超过(|S|+1)/2=3，所以至少存在一种重排方案。这时我们要确定重排之后的第一个字符。由于我们希望字典序最小，所以我们 会先尝试第一个字符是’a’行不行。假设第一个字符是’a’，那么剩余的S’=”bbbc”，这时剩余的S是INVALID，所以我们不能把’a’放在一个字符。
然后我们再尝试把’b’放在第一个字符。这时剩余的S’是”bbac”，我们知道”bbac”至少存在一个解，并且这个解不需要第一个字符一定是’b’(因为如果S’的解需要第一个字符一定是某个ch，那么S=S’+ch一定INVALID，大家可以仔细想想）。所以我们可以安全的令第一个字符是’b’，一定是字典序最小的选择。
同样的贪心策略处理3个字符后之后，我们就会得到前3个字符是：”bab”，这时余下的字符是”bc”。注意由于前一个字符是’b’，所以此时字典序的第一选择’b’不能被选（尽管出去’b’之后剩余字符仍 然有解），所以第四个字符选’c’。
最终我们得到答案：”babcb”。
本题的关键就是每一个字符选择时，都需要判断剩余字符有没有解。由于只有’a’-‘z’26个字母，判断有没有解可以认为是O(26)=O(1)即常数复杂度的。所以总复杂度是O(|S|)。
1 | #include <bits/stdc++.h> |
