https://leetcode.com/problems/reorganize-string/description/
767. Reorganize String
給你一個字串 s，求出這個 s 是否可以透過重排列得到一個相鄰字元都不相同的字串，
若可以則返回任意的結果，否則返回""。
Example 1:
Input: s = "aab"
Output: "aba"
Example 2:
Input: s = "aaab"
Output: ""
思路：
1.用貪婪去想，如果一個字串相鄰字串都不相同，那麼出現次數比較多的字元先放在
前面才比較有機會在後面不相鄰。
2.用 count 統計每個字母的出現次數，used 統計這輪是不是已經用過所有字母。
3.每輪都從還沒排列的字元列表中取出出現最多次的字元去排列，如果和前一個字元
不相同或就把他插入並更新次數，如果不同就嘗試其他沒用過的字元。
4.如果每個字元都用過但是滿足不了條件就提早返回 ""，否則不斷 loop 直到構建的
字串長度等於 s 的長度即可。
Java Code：
--------------------------------------
class Solution {
public String reorganizeString(String s) {
int[] count = new int[26];
boolean[] used = new boolean[26];
for (char c : s.toCharArray()) {
count[c - 'a']++;
}
StringBuilder sb = new StringBuilder();
while (sb.length() != s.length()) {
int index = getMaxCount(count, used);
if (index == -1) return "";
if (sb.length() == 0 ||
sb.charAt(sb.length() - 1) != ('a' + index)) {
count[index]--;
sb.append((char)('a' + index));
used = new boolean[26];
} else {
used[index] = true;
}
}
return sb.toString();
}
private int getMaxCount(int[] count, boolean[] used) {
int index = -1;
int maxCount = 0;
for (int i = 0; i < 26; i++) {
if (used[i]) continue;
if (count[i] > maxCount) {
maxCount = count[i];
index = i;
}
}
return index;
}
}
--------------------------------------
--
https://i.imgur.com/uiFto42.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1692791924.A.546.html