add a solution for 159

fishercoder1534 · fishercoder1534 · commit 4dd42b48a8ba · 2021-10-20T16:35:58.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_159.java b/src/main/java/com/fishercoder/solutions/_159.java
@@ -33,4 +33,39 @@ public int lengthOfLongestSubstringTwoDistinct(String s) {
             return maxLength;
         }
     }
+
+    public static class Solution2 {
+        /**
+         * My completely original solution, classic sliding window problem:
+         * use two pointers, one keeps moving towards the right to expand;
+         * the other moves only when we are no longer meeting the requirement, i.e. shrinks.
+         */
+        public int lengthOfLongestSubstringTwoDistinct(String s) {
+            int distinct = 0;
+            int ans = 0;
+            int left = 0;
+            int right = 0;
+            int[] counts = new int[256];
+            while (right < s.length()) {
+                char c1 = s.charAt(right);
+                if (counts[c1] == 0) {
+                    distinct++;
+                }
+                counts[c1]++;
+                right++;
+                if (distinct <= 2) {
+                    ans = Math.max(ans, right - left);
+                }
+                while (distinct > 2) {
+                    char c2 = s.charAt(left);
+                    counts[c2]--;
+                    if (counts[c2] == 0) {
+                        distinct--;
+                    }
+                    left++;
+                }
+            }
+            return ans;
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/_159Test.java b/src/test/java/com/fishercoder/_159Test.java
@@ -0,0 +1,38 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._159;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _159Test {
+    private static _159.Solution1 solution1;
+    private static _159.Solution2 solution2;
+    private static String s;
+    private static int expected;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _159.Solution1();
+        solution2 = new _159.Solution2();
+    }
+
+    @Test
+    public void test1() {
+        s = "eceba";
+        expected = 3;
+        assertEquals(expected, solution1.lengthOfLongestSubstringTwoDistinct(s));
+        assertEquals(expected, solution2.lengthOfLongestSubstringTwoDistinct(s));
+    }
+
+
+    @Test
+    public void test2() {
+        s = "ccaabbb";
+        expected = 5;
+        assertEquals(expected, solution1.lengthOfLongestSubstringTwoDistinct(s));
+        assertEquals(expected, solution2.lengthOfLongestSubstringTwoDistinct(s));
+    }
+
+}
