Update Reorganize String.java

varunu28 · web-flow · commit fc59cb84f7af · 2022-09-06T07:43:06.000-07:00
diff --git a/Medium/Reorganize String.java b/Medium/Reorganize String.java
@@ -1,44 +1,37 @@
 class Solution {
-    public String reorganizeString(String S) {
-        int buffer = S.length()%2 == 0 ? S.length()/2 : S.length()/2 + 1;
-        Map<Character, Integer> map = new HashMap<>();
-        char[] chars = S.toCharArray();
-
-        for (char c : chars) {
-            map.put(c, map.getOrDefault(c, 0) + 1);
-            if (map.get(c) > buffer) {
-                return "";
-            }
-        }
-
-        return createString(map);
+  public String reorganizeString(String s) {
+    Map<Character, Integer> map = new HashMap<>();
+    for (char c : s.toCharArray()) {
+      map.put(c, map.getOrDefault(c, 0) + 1);
     }
-
-    private String createString(Map<Character, Integer> map) {
-        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[1] - a[1]);
-        for (char c : map.keySet()) {
-            pq.add(new int[] {c, map.get(c)});
-        }
-
-        StringBuilder sb = new StringBuilder();
-        while (!pq.isEmpty()) {
-            int[] first = pq.poll();
-            if (sb.length() == 0 || first[0] != sb.charAt(sb.length() - 1)) {
-                sb.append((char) first[0]);
-                if (--first[1] > 0) {
-                    pq.add(first);
-                }
-            }
-            else {
-                int[] second = pq.poll();
-                sb.append((char) second[0]);
-                if (--second[1] > 0) {
-                    pq.add(second);
-                }
-                pq.add(first);
-            }
+    PriorityQueue<Character> pq = new PriorityQueue<>(
+        (o1, o2) -> map.get(o2).compareTo(map.get(o1)));
+    pq.addAll(map.keySet());
+    StringBuilder sb = new StringBuilder();
+    while (!pq.isEmpty()) {
+      char removed = pq.poll();
+      if (!sb.isEmpty() && sb.charAt(sb.length() - 1) == removed) {
+        if (pq.isEmpty()) {
+          return "";
         }
+        char secondRemoved = pq.poll();
+        pq.add(removed);
+        sb.append(secondRemoved);
+        updateStructure(map, pq, secondRemoved);
+      } else {
+        sb.append(removed);
+        updateStructure(map, pq, removed);
+      }
+    }
+    return sb.toString();
+  }
 
-        return sb.toString();
+  private void updateStructure(Map<Character, Integer> map, PriorityQueue<Character> pq, char c) {
+    map.put(c, map.get(c) - 1);
+    if (map.get(c) > 0) {
+      pq.add(c);
+    } else {
+      map.remove(c);
     }
+  }
 }
