1
class Solution {
2
  public String reorganizeString(String s) {
3
    StringBuilder ans = new StringBuilder("");
4
    char[] charArray = new char[s.length()];
5
    Map<Character, Integer> hashMap = new HashMap<>();
6
    Queue<CharOccurence> queue = new PriorityQueue<>((a, b) -> b.occurence - a.occurence);
7

8
    charArray = s.toCharArray();
9

10
    for (int i = 0; i < charArray.length; i++) {
11
      Integer occurence = hashMap.get(charArray[i]);
12
      if (occurence == null) hashMap.put(charArray[i], 1);
13
      else hashMap.put(charArray[i], occurence + 1);
14
    }
15
    queue.addAll(
16
        hashMap.entrySet().stream()
17
            .parallel()
18
            .map(e -> new CharOccurence(e.getKey(), e.getValue()))
19
            .collect(Collectors.toList()));
20
    while (!queue.isEmpty()) {
21
      Queue<CharOccurence> tmpQueue = new LinkedList<>();
22
      int sizeQueue = queue.size();
23
      int stringLength = ans.length();
24
      int startSub = (stringLength - 1 < 0) ? 0 : stringLength - 1;
25
      int endSub = stringLength;
26
      String lastLetter = ans.substring(startSub, endSub);
27
      boolean letterAdded = false;
28
      for (int i = 0; i < sizeQueue; i++) {
29
        CharOccurence letter = queue.poll();
30
        if (!lastLetter.contains(String.valueOf(letter.letter))) {
31
          letter.occurence--;
32
          ans.append(String.valueOf(letter.letter));
33
          if (letter.occurence > 0) tmpQueue.add(letter);
34
          letterAdded = true;
35
          break;
36
        } else {
37
          tmpQueue.add(letter);
38
        }
39
      }
40
      if (!letterAdded) return "";
41
      queue.addAll(tmpQueue);
42
    }
43
    return ans.toString();
44
  }
45

46
  class CharOccurence {
47
    public Character letter;
48
    public int occurence;
49

50
    public CharOccurence(Character letter, int occurence) {
51
      this.letter = letter;
52
      this.occurence = occurence;
53
    }
54
  }
55
}