add a solution for 340

fishercoder1534 · fishercoder1534 · commit f38e2c2af17b · 2021-10-20T16:48:16.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_340.java b/src/main/java/com/fishercoder/solutions/_340.java
@@ -21,7 +21,6 @@ public int lengthOfLongestSubstringKDistinct(String s, int k) {
                 if (num > k) {
                     while (--count[s.charAt(left++)] > 0) {
                     }
-                    ;
                     num--;
                 }
                 result = Math.max(result, right - left + 1);
@@ -57,4 +56,35 @@ public int lengthOfLongestSubstringKDistinct(String s, int k) {
         }
     }
 
+    public static class Solution3 {
+        /**
+         * My original solution on 10/20/2021, a very generic sliding window template.
+         */
+        public int lengthOfLongestSubstringKDistinct(String s, int k) {
+            int left = 0;
+            int right = 0;
+            int ans = 0;
+            int[] count = new int[256];
+            int distinctCount = 0;
+            while (right < s.length()) {
+                if (count[s.charAt(right)] == 0) {
+                    distinctCount++;
+                }
+                count[s.charAt(right)]++;
+                right++;
+                if (distinctCount <= k) {
+                    ans = Math.max(ans, right - left);
+                }
+                while (distinctCount > k) {
+                    count[s.charAt(left)]--;
+                    if (count[s.charAt(left)] == 0) {
+                        distinctCount--;
+                    }
+                    left++;
+                }
+            }
+            return ans;
+        }
+    }
+
 }
diff --git a/src/test/java/com/fishercoder/_340Test.java b/src/test/java/com/fishercoder/_340Test.java
@@ -9,17 +9,26 @@
 public class _340Test {
     private static _340.Solution1 solution1;
     private static _340.Solution2 solution2;
+    private static _340.Solution3 solution3;
+    private static String s;
+    private static int k;
+    private static int expected;
 
     @BeforeClass
     public static void setup() {
         solution1 = new _340.Solution1();
         solution2 = new _340.Solution2();
+        solution3 = new _340.Solution3();
     }
 
     @Test
     public void test1() {
-        assertEquals(3, solution1.lengthOfLongestSubstringKDistinct("eceba", 2));
-        assertEquals(3, solution2.lengthOfLongestSubstringKDistinct("eceba", 2));
+        s = "eceba";
+        k = 2;
+        expected = 3;
+        assertEquals(expected, solution1.lengthOfLongestSubstringKDistinct(s, k));
+        assertEquals(expected, solution2.lengthOfLongestSubstringKDistinct(s, k));
+        assertEquals(expected, solution3.lengthOfLongestSubstringKDistinct(s, k));
     }
 
     @Test
