add 767

fishercoder1534 · fishercoder1534 · commit b175ff3efbfb · 2018-01-20T21:19:00.000-08:00
diff --git a/README.md b/README.md
@@ -22,6 +22,7 @@ Your ideas/fixes/algorithms are more than welcome!
 
 |  #  |      Title     |   Solutions   | Time          | Space         | Video  | Difficulty  | Tag                   
 |-----|----------------|---------------|---------------|---------------|--------|-------------|-------------
+|767|[Reorganize String](https://leetcode.com/problems/reorganize-string/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_767.java) | O(klogk) k is the number of unique characters in given String| O(k) | |Medium|
 |766|[Toeplitz Matrix](https://leetcode.com/problems/toeplitz-matrix/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_766.java) | O(m*n) | O(1) | |Easy|
 |765|[Couples Holding Hands](https://leetcode.com/problems/couples-holding-hands/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_765.java) | O(n^2) | O(1) | |Hard| 
 |764|[Largest Plus Sign](https://leetcode.com/problems/largest-plus-sign/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_764.java) | O(n^2) | O(n^2) | |Medium| DP
diff --git a/src/main/java/com/fishercoder/solutions/_767.java b/src/main/java/com/fishercoder/solutions/_767.java
@@ -0,0 +1,83 @@
+package com.fishercoder.solutions;
+
+import java.util.HashMap;
+import java.util.Map;
+import java.util.PriorityQueue;
+
+/**
+ * 767. Reorganize String
+ *
+ * Given a string S, check if the letters can be rearranged so that two characters that are adjacent to each other are not the same.
+
+ If possible, output any possible result.  If not possible, return the empty string.
+
+ Example 1:
+
+ Input: S = "aab"
+ Output: "aba"
+
+ Example 2:
+
+ Input: S = "aaab"
+ Output: ""
+
+ Note:
+
+ S will consist of lowercase letters and have length in range [1, 500].
+ */
+
+public class _767 {
+  public static class Solution1 {
+    public String reorganizeString(String S) {
+      Map<Character, Integer> map = new HashMap<>();
+      for (char c : S.toCharArray()) {
+        map.put(c, map.getOrDefault(c, 0) + 1);
+      }
+      int len = S.length();
+      for (char c : map.keySet()) {
+        if ((len % 2 == 0 && map.get(c) > len / 2) || (len % 2 != 0 && map.get(c) >= len / 2 + 2)) {
+          return "";
+        }
+      }
+      PriorityQueue<CustChar> queue = new PriorityQueue<>((a, b) -> b.count - a.count);
+      for (char c : map.keySet()) {
+        queue.offer(new CustChar(c, map.get(c)));
+      }
+
+      StringBuilder sb = new StringBuilder();
+      while (!queue.isEmpty()) {
+        CustChar curr = queue.poll();
+        char c = curr.c;
+        if (sb.length() > 0 && sb.charAt(sb.length() - 1) != c) {
+          sb.append(c);
+          if (curr.count > 1) {
+            queue.offer(new CustChar(c, curr.count - 1));
+          }
+        } else if (sb.length() == 0) {
+          sb.append(c);
+          if (curr.count > 1) {
+            queue.offer(new CustChar(c, curr.count - 1));
+          }
+        } else if (sb.length() > 0 && sb.charAt(sb.length() - 1) == c && !queue.isEmpty()) {
+          CustChar next = queue.poll();
+          sb.append(next.c);
+          if (next.count > 1) {
+            queue.offer(new CustChar(next.c, next.count - 1));
+          }
+          queue.offer(curr);
+        }
+      }
+      return sb.toString();
+    }
+
+    class CustChar {
+      Character c;
+      int count;
+
+      public CustChar(Character 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
@@ -0,0 +1,36 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._767;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+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"));
+  }
+}
