add a solution for 1209

fishercoder1534 · fishercoder1534 · commit f3bc0e2acbb4 · 2022-01-06T18:19:33.000-08:00
diff --git a/src/main/java/com/fishercoder/solutions/_1209.java b/src/main/java/com/fishercoder/solutions/_1209.java
@@ -1,5 +1,7 @@
 package com.fishercoder.solutions;
 
+import java.util.Deque;
+import java.util.LinkedList;
 import java.util.Stack;
 
 public class _1209 {
@@ -72,4 +74,45 @@ public String removeDuplicates(String s, int k) {
             return sb.toString();
         }
     }
+
+    public static class Solution3 {
+        /**
+         * My completely original solution on 1/6/2021.
+         */
+        class CharCount {
+            char c;
+            int count;
+
+            public CharCount(char c, int count) {
+                this.c = c;
+                this.count = count;
+            }
+        }
+
+        public String removeDuplicates(String s, int k) {
+            Deque<CharCount> stack = new LinkedList<>();
+            for (char c : s.toCharArray()) {
+                if (stack.isEmpty()) {
+                    stack.addLast(new CharCount(c, 1));
+                } else {
+                    if (stack.peekLast().c == c && stack.peekLast().count + 1 == k) {
+                        stack.pollLast();
+                    } else if (stack.peekLast().c == c) {
+                        stack.addLast(new CharCount(c, stack.pollLast().count + 1));
+                    } else {
+                        stack.addLast(new CharCount(c, 1));
+                    }
+                }
+            }
+            StringBuilder sb = new StringBuilder();
+            while (!stack.isEmpty()) {
+                CharCount pair = stack.pollLast();
+                int count = pair.count;
+                while (count-- > 0) {
+                    sb.append(pair.c);
+                }
+            }
+            return sb.reverse().toString();
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/_1209Test.java b/src/test/java/com/fishercoder/_1209Test.java
@@ -10,35 +10,41 @@ public class _1209Test {
 
     private static _1209.Solution1 solution1;
     private static _1209.Solution2 solution2;
+    private static _1209.Solution3 solution3;
 
     @BeforeClass
     public static void setup() {
         solution1 = new _1209.Solution1();
         solution2 = new _1209.Solution2();
+        solution3 = new _1209.Solution3();
     }
 
     @Test
     public void test1() {
         assertEquals("abcd", solution1.removeDuplicates("abcd", 2));
         assertEquals("abcd", solution2.removeDuplicates("abcd", 2));
+        assertEquals("abcd", solution3.removeDuplicates("abcd", 2));
     }
 
     @Test
     public void test2() {
         assertEquals("aa", solution1.removeDuplicates("deeedbbcccbdaa", 3));
         assertEquals("aa", solution2.removeDuplicates("deeedbbcccbdaa", 3));
+        assertEquals("aa", solution3.removeDuplicates("deeedbbcccbdaa", 3));
     }
 
     @Test
     public void test3() {
         assertEquals("ps", solution1.removeDuplicates("pbbcggttciiippooaais", 2));
         assertEquals("ps", solution2.removeDuplicates("pbbcggttciiippooaais", 2));
+        assertEquals("ps", solution3.removeDuplicates("pbbcggttciiippooaais", 2));
     }
 
     @Test
     public void test4() {
         assertEquals("ghayqgq", solution1.removeDuplicates("ghanyhhhhhttttttthhyyyyyynnnnnnyqkkkkkkkrrrrrrjjjjjjjryyyyyyfffffffygq", 7));
         assertEquals("ghayqgq", solution2.removeDuplicates("ghanyhhhhhttttttthhyyyyyynnnnnnyqkkkkkkkrrrrrrjjjjjjjryyyyyyfffffffygq", 7));
+        assertEquals("ghayqgq", solution3.removeDuplicates("ghanyhhhhhttttttthhyyyyyynnnnnnyqkkkkkkkrrrrrrjjjjjjjryyyyyyfffffffygq", 7));
     }
 
 }
