### 题目

Given a string S, check if the letters can be rearranged so that two characters that are adjacent to each other are not the same.

If possible, output any possible result. If not possible, return the empty string.

Example 1:

Input: S = "aab"
Output: "aba"


Example 2:

Input: S = "aaab"
Output: ""


Note:

• S will consist of lowercase letters and have length in range [1, 500].

### 系统性地解决问题

numOther < numX - 1

a a a a a
^ ^ ^ ^
b b b b


先填5个a
| a |   | a |   | a |   | a |   | a |

| a | b | a | b | a | b | a | b | a |


#### 代码

class Solution {
public String reorganizeString(String S) {
int size = S.length();
if (size < 2) return S;
int[][] counts = new int[26][2];
for (int i = 0; i < 26; i++) {
counts[i][1] = i + 'a';
}
char[] cs = S.toCharArray();
for (char c : cs) {
counts[c - 'a'][0]++;
}
Arrays.sort(counts, (int[] a, int[] b) -> b[0] - a[0]);
int max = counts[0][0];
if (max > (size + 1) / 2) return "";
char[] arr = new char[size];
int idx = 0;
char c = (char) counts[idx][1];
int count = counts[idx][0];
boolean repeat = false;
for (int i = 0; i < size; i += 2) {
if (count == 0) {
c = (char) counts[++idx][1];
count = counts[idx][0];
}
arr[i] = c;
count--;
if (!repeat && i + 2 >= size) {
i = -1;
repeat = true;
}
}
return new String(arr);
}
}


### 交换法

  swap
|   |
aaaaabbbb

abaaaabbb


    后面再也找不到不是a的字母
|
cxawaaa

c x a w a
^ ^
a a


#### 代码

class Solution {
public String reorganizeString(String S) {
int size = S.length();
if (size < 2) return S;
char[] arr = S.toCharArray();
for (int pre = 0, curr = 1; curr < size; pre++, curr++) {
if (arr[pre] == arr[curr]) {
int idx = curr + 1;
while (idx < size && arr[idx] == arr[curr]) idx++;
if (idx == size) {
char[] filled = fill(Arrays.copyOfRange(arr, 0, pre), arr[pre], size - pre);
return (filled == null)? "" : new String(filled);
}
arr[curr] = arr[idx];
arr[idx] = arr[pre];
}
}
return new String(arr);
}

private char[] fill(char[] arr, char c, int count) {
char[] res = new char[arr.length + count];
int i = 0;
int idx = 0;
for (; i < arr.length && count > 0; i++) {
if (arr[i] != c) {
res[idx++] = c;
res[idx++] = arr[i];
count--;
} else {
res[idx++] = c;
if (i + 1 < arr.length) {
res[idx++] = arr[++i];
}
}
}
if (idx < res.length && count > 0) {
res[idx++] = c;
count--;
}
if (count > 0) return null;
while (i < arr.length) {
res[idx++] = arr[i++];
}
return res;
}
}