Reorganize String
给一个string, 问能不能重组它, 让每个相邻字符都不一样.
这个题用可以sort可以用pq, 我用的pq.
class Solution {
class Pair {
int count;
char c;
Pair(int count, char c) {
this.count = count;
this.c = c;
}
}
Map<Character, Integer> map = new HashMap<>();
public String reorganizeString(String S) {
for(char c : S.toCharArray()) {
map.putIfAbsent(c, 0);
map.put(c, map.get(c) + 1);
}
PriorityQueue<Pair> pairs = new PriorityQueue<>((a, b) -> (b.count - a.count));
for(Map.Entry<Character, Integer> e : map.entrySet()) {
pairs.add(new Pair(e.getValue(), e.getKey()));
}
StringBuilder sb = new StringBuilder();
while(!pairs.isEmpty()) {
Pair p = pairs.poll();
if(sb.length() >= 1 && sb.charAt(sb.length() - 1) == p.c) {
Pair pp = pairs.poll();
if(pp == null) {
return "";
}
pp.count --;
sb.append(pp.c);
if(pp.count != 0)
pairs.add(pp);
}
p.count--;
sb.append(p.c);
if(p.count != 0)
pairs.add(p);
}
return sb.toString();
}
}