blob: 7a42643766a58f62ca6e33eef0afdfa6c19602ec (
plain)
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
|
// 767. Reorganize String
#include "leetcode.h"
/*
* given a string 's', rearrange the characters of 's' so that any two adjacent
* characters are not the same. return any possible arrangement of 's', or
* return "" if not possible.
*/
class Solution {
public:
string reorganizeString(string s) {
vector<int> cnt(26);
int most_freq = 0, i = 0;
for (char c : s)
if (++cnt[c - 'a'] > cnt[most_freq])
most_freq = (c - 'a');
if (2 * cnt[most_freq] - 1 > s.size())
return "";
while (cnt[most_freq]) {
s[i] = ('a' + most_freq);
i += 2;
cnt[most_freq]--;
}
for (int j = 0; j < 26; j++)
while (cnt[j]) {
if (i >= s.size())
i = 1;
s[i] = ('a' + j);
cnt[j]--;
i += 2;
}
return s;
}
};
int main() {
Solution obj;
cout << obj.reorganizeString("aab"); // expect: aba
cout << obj.reorganizeString("aaab"); // expect:
}
|