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
| class Solution {
public String reorganizeString(String s) {
char[] chars = s.toCharArray();
int[] countMap = new int[26];
for (char c : chars) {
countMap[c - 'a']++;
}
int maxCount = 0, threshold = (s.length() + 1) / 2;
char mostChar = ' ';
for (int i = 0; i < countMap.length; i++) {
if (countMap[i] > maxCount) {
maxCount = countMap[i];
if (maxCount > threshold) {
return "";
}
mostChar = (char) ('a' + i);
}
}
int index = 0;
for (int i = 0; i < maxCount; i++) {
chars[index] = mostChar;
index += 2;
}
countMap[mostChar - 'a'] = 0;
for (int i = 0; i < countMap.length; i++) {
char c = (char) ('a' + i);
for (int j = 0; j < countMap[i]; j++) {
if (index >= chars.length) {
index = 1;
}
chars[index] = c;
index += 2;
}
}
return new String(chars);
}
}
|