add 830

fishercoder1534 · fishercoder1534 · commit ab7561b3fe26 · 2018-05-06T08:08:58.000-07: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                   
 |-----|----------------|---------------|---------------|---------------|--------|-------------|-------------
+|830|[Positions of Large Groups](https://leetcode.com/problems/positions-of-large-groups/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_830.java) | O(n) | O(n) | |Easy|
 |824|[Goat Latin](https://leetcode.com/problems/goat-latin/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_824.java) | O(n) | O(1) | |Easy| 
 |821|[Shortest Distance to a Character](https://leetcode.com/problems/shortest-distance-to-a-character/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_821.java) | O(n) | O(k) (k is the number of char C in S) | |Easy| 
 |819|[Most Common Word](https://leetcode.com/problems/most-common-word/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_819.java) | O(m+n) | O(n) | |Easy| HashMap
diff --git a/src/main/java/com/fishercoder/solutions/_830.java b/src/main/java/com/fishercoder/solutions/_830.java
@@ -0,0 +1,50 @@
+package com.fishercoder.solutions;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+
+/**
+ * 830. Positions of Large Groups
+ *
+ * In a string S of lowercase letters, these letters form consecutive groups of the same character.
+ * For example, a string like S = "abbxxxxzyy" has the groups "a", "bb", "xxxx", "z" and "yy".
+ * Call a group large if it has 3 or more characters.  We would like the starting and ending positions of every large group.
+ * The final answer should be in lexicographic order.
+ *
+ * Example 1:
+ * Input: "abbxxxxzzy"
+ * Output: [[3,6]]
+ * Explanation: "xxxx" is the single large group with starting  3 and ending positions 6.
+ *
+ * Example 2:
+ * Input: "abc"
+ * Output: []
+ * Explanation: We have "a","b" and "c" but no large group.
+ *
+ * Example 3:
+ * Input: "abcdddeeeeaabbbcd"
+ * Output: [[3,5],[6,9],[12,14]]
+ *
+ * Note:  1 <= S.length <= 1000
+ */
+public class _830 {
+  public static class Solution1 {
+    public List<List<Integer>> largeGroupPositions(String S) {
+      List<List<Integer>> result = new ArrayList<>();
+      char[] chars = S.toCharArray();
+      for (int i = 0; i < chars.length;) {
+        char first = chars[i];
+        int j = i+1;
+        while (j < chars.length && first == chars[j]) {
+          j++;
+        }
+        if ((j - i) >= 3) {
+          result.add(Arrays.asList(i, j - 1));
+        }
+        i = j;
+      }
+      return result;
+    }
+  }
+}
diff --git a/src/test/java/com/fishercoder/_830Test.java b/src/test/java/com/fishercoder/_830Test.java
@@ -0,0 +1,42 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._830;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _830Test {
+  private static _830.Solution1 solution1;
+  private static List<List<Integer>> expected;
+
+  @BeforeClass
+  public static void setup() {
+    solution1 = new _830.Solution1();
+  }
+
+  @Test
+  public void test1() {
+    expected = new ArrayList<>();
+    expected.add(Arrays.asList(3, 6));
+    assertEquals(expected, solution1.largeGroupPositions("abbxxxxzzy"));
+  }
+
+  @Test
+  public void test2() {
+    expected = new ArrayList<>();
+    assertEquals(expected, solution1.largeGroupPositions("abc"));
+  }
+
+  @Test
+  public void test3() {
+    expected = new ArrayList<>();
+    expected.add(Arrays.asList(3, 5));
+    expected.add(Arrays.asList(6, 9));
+    expected.add(Arrays.asList(12, 14));
+    assertEquals(expected, solution1.largeGroupPositions("abcdddeeeeaabbbcd"));
+  }
+}
