友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
767. 重构字符串
给定一个字符串 s，检查是否能重新排布其中的字母，使得两相邻的字符不同。
返回 s 的任意可能的重新排列。若不可行，返回空字符串 ""。
示例 1:
输入: s = "aab" 输出: "aba"
示例 2:
输入: s = "aaab" 输出: ""
提示:
-
1 <= s.length <= 500 -
s只包含小写字母
思路分析
贪心：统计每个字符出现次数，安装次数倒序插入到已有字符串中。
-
一刷
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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-06-10 23:01:52
*/
public String reorganizeString(String s) {
Map<Character, Integer> map = new HashMap<>();
for (char c : s.toCharArray()) {
map.put(c, map.getOrDefault(c, 0) + 1);
}
PriorityQueue<Map.Entry<Character, Integer>> queue = new PriorityQueue<>(
Map.Entry.<Character, Integer>comparingByValue().reversed()
.thenComparing(Map.Entry.comparingByKey()));
for (Map.Entry<Character, Integer> entry : map.entrySet()) {
queue.offer(entry);
}
if (s.length() % 2 == 0
? (queue.peek().getValue() >= s.length() / 2 + 1)
: (queue.peek().getValue() > s.length() / 2 + 1)) {
return "";
}
StringBuilder sb = new StringBuilder();
int index = -1;
while (!queue.isEmpty()) {
Map.Entry<Character, Integer> entry = queue.poll();
if (sb.isEmpty()) {
sb.repeat(entry.getKey().toString(), entry.getValue());
index = sb.length() - 1;
} else {
for (int i = 0; i < entry.getValue() && index >= 0; i++) {
sb.insert(index, entry.getKey());
index--;
if (index < 0) {
index = sb.length() - 1;
}
}
}
}
return sb.toString();
}