add a solution for 767

fishercoder1534 · fishercoder1534 · commit 9c79a76b6bb7 · 2021-12-24T17:23:27.000-08:00
diff --git a/src/main/java/com/fishercoder/solutions/_767.java b/src/main/java/com/fishercoder/solutions/_767.java
@@ -58,4 +58,47 @@ public CustChar(Character c, int count) {
             }
         }
     }
+
+    public static class Solution2 {
+        /**
+         * My completely original solution on 12/24/2021.
+         */
+        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<Tuple> maxHeap = new PriorityQueue<>((a, b) -> b.count - a.count);
+            for (char c : map.keySet()) {
+                maxHeap.add(new Tuple(c, map.get(c)));
+            }
+            StringBuilder sb = new StringBuilder("1");
+            while (!maxHeap.isEmpty()) {
+                PriorityQueue<Tuple> tmp = new PriorityQueue<>((a, b) -> b.count - a.count);
+                Tuple curr = maxHeap.poll();
+                while (sb.length() != 0 && sb.charAt(sb.length() - 1) == curr.c && !maxHeap.isEmpty()) {
+                    tmp.offer(curr);
+                    curr = maxHeap.poll();
+                }
+                if (curr.c != sb.charAt(sb.length() - 1)) {
+                    sb.append(curr.c);
+                }
+                maxHeap.addAll(tmp);
+                if (curr.count > 1) {
+                    maxHeap.offer(new Tuple(curr.c, curr.count - 1));
+                }
+            }
+            return sb.substring(1).length() != s.length() ? "" : sb.substring(1);
+        }
+
+        class Tuple {
+            char c;
+            int count;
+
+            public Tuple(char c, int count) {
+                this.c = c;
+                this.count = count;
+            }
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/_767Test.java b/src/test/java/com/fishercoder/_767Test.java
@@ -7,30 +7,36 @@
 import static org.junit.Assert.assertEquals;
 
 public class _767Test {
-  private static _767.Solution1 solution1;
-
-  @BeforeClass
-  public static void setup() {
-    solution1 = new _767.Solution1();
-  }
-
-  @Test
-  public void test1() {
-    assertEquals("aba", solution1.reorganizeString("aab"));
-  }
-
-  @Test
-  public void test2() {
-    assertEquals("", solution1.reorganizeString("aaab"));
-  }
-
-  @Test
-  public void test3() {
-    assertEquals("bababab", solution1.reorganizeString("aaabbbb"));
-  }
-
-  @Test
-  public void test4() {
-    assertEquals("vovlv", solution1.reorganizeString("vvvlo"));
-  }
+    private static _767.Solution1 solution1;
+    private static _767.Solution2 solution2;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _767.Solution1();
+        solution2 = new _767.Solution2();
+    }
+
+    @Test
+    public void test1() {
+        assertEquals("aba", solution1.reorganizeString("aab"));
+        assertEquals("aba", solution2.reorganizeString("aab"));
+    }
+
+    @Test
+    public void test2() {
+        assertEquals("", solution1.reorganizeString("aaab"));
+        assertEquals("", solution2.reorganizeString("aaab"));
+    }
+
+    @Test
+    public void test3() {
+        assertEquals("bababab", solution1.reorganizeString("aaabbbb"));
+        assertEquals("bababab", solution2.reorganizeString("aaabbbb"));
+    }
+
+    @Test
+    public void test4() {
+        assertEquals("vovlv", solution1.reorganizeString("vvvlo"));
+        assertEquals("vovlv", solution2.reorganizeString("vvvlo"));
+    }
 }
