add a solution for 3

fishercoder1534 · fishercoder1534 · commit 9f46e091620c · 2021-10-20T19:17:30.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_3.java b/src/main/java/com/fishercoder/solutions/_3.java
@@ -120,4 +120,44 @@ public int lengthOfLongestSubstring(String s) {
             return longest;
         }
     }
+
+    public static class Solution6 {
+        /**
+         * Sliding Window, my completely original idea on 10/20/2021. Although less efficient then Solution5, it follows a generic template without any manipulation.
+         * Basically, keep moving the left boundary towards the right and keep updating the result along the way.
+         * O(n) time
+         * O(n) space
+         */
+
+        public int lengthOfLongestSubstring(String s) {
+            int left = 0;
+            int right = 0;
+            int ans = 0;
+            Map<Character, Integer> map = new HashMap<>();
+            while (right < s.length()) {
+                map.put(s.charAt(right), map.getOrDefault(s.charAt(right), 0) + 1);
+                right++;
+                if (allUnique(map)) {
+                    ans = Math.max(ans, right - left);
+                }
+                while (!allUnique(map)) {
+                    map.put(s.charAt(left), map.get(s.charAt(left)) - 1);
+                    if (map.get(s.charAt(left)) == 0) {
+                        map.remove(s.charAt(left));
+                    }
+                    left++;
+                }
+            }
+            return ans;
+        }
+
+        private boolean allUnique(Map<Character, Integer> map) {
+            for (char key : map.keySet()) {
+                if (map.get(key) > 1) {
+                    return false;
+                }
+            }
+            return true;
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/_3Test.java b/src/test/java/com/fishercoder/_3Test.java
@@ -12,6 +12,9 @@ public class _3Test {
     private static _3.Solution3 solution3;
     private static _3.Solution4 solution4;
     private static _3.Solution5 solution5;
+    private static _3.Solution6 solution6;
+    private static int expected;
+    private static String s;
 
     @BeforeClass
     public static void setup() {
@@ -20,15 +23,19 @@ public static void setup() {
         solution3 = new _3.Solution3();
         solution4 = new _3.Solution4();
         solution5 = new _3.Solution5();
+        solution6 = new _3.Solution6();
     }
 
     @Test
     public void test1() {
-        assertEquals(3, solution1.lengthOfLongestSubstring("abcabcbb"));
-        assertEquals(3, solution2.lengthOfLongestSubstring("abcabcbb"));
-        assertEquals(3, solution3.lengthOfLongestSubstring("abcabcbb"));
-        assertEquals(3, solution4.lengthOfLongestSubstring("abcabcbb"));
-        assertEquals(3, solution5.lengthOfLongestSubstring("abcabcbb"));
+        expected = 3;
+        s = "abcabcbb";
+        assertEquals(expected, solution1.lengthOfLongestSubstring(s));
+        assertEquals(expected, solution2.lengthOfLongestSubstring(s));
+        assertEquals(expected, solution3.lengthOfLongestSubstring(s));
+        assertEquals(expected, solution4.lengthOfLongestSubstring(s));
+        assertEquals(expected, solution5.lengthOfLongestSubstring(s));
+        assertEquals(expected, solution6.lengthOfLongestSubstring(s));
     }
 
 }
