add a solution for 424

fishercoder1534 · fishercoder1534 · commit aed3eab9779e · 2021-10-20T17:24:06.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_424.java b/src/main/java/com/fishercoder/solutions/_424.java
@@ -1,5 +1,8 @@
 package com.fishercoder.solutions;
 
+import java.util.HashSet;
+import java.util.Set;
+
 public class _424 {
 
     public static class Solution1 {
@@ -21,4 +24,46 @@ public int characterReplacement(String s, int k) {
             return maxLength;
         }
     }
+
+    public static class Solution2 {
+        /**
+         * My original solution using Sliding Window technique:
+         * I try to use each character as the possible candidate to find all solutions and compare.
+         */
+        public int characterReplacement(String s, int k) {
+            Set<Character> set = new HashSet<>();
+            for (char c : s.toCharArray()) {
+                set.add(c);
+            }
+            int ans = 0;
+            for (char c : set) {
+                ans = Math.max(ans, slidingWindow(c, s, k));
+            }
+            return ans;
+        }
+
+        private int slidingWindow(char c, String s, int k) {
+            int left = 0;
+            int right = 0;
+            int ans = 0;
+            while (right < s.length()) {
+                if (s.charAt(right) != c) {
+                    if (k > 0) {
+                        k--;
+                        right++;
+                    } else {
+                        while (left < s.length() && s.charAt(left) == c) {
+                            left++;
+                        }
+                        left++;
+                        k++;
+                    }
+                } else {
+                    right++;
+                }
+                ans = Math.max(ans, right - left);
+            }
+            return ans;
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/_424Test.java b/src/test/java/com/fishercoder/_424Test.java
@@ -8,67 +8,63 @@
 
 public class _424Test {
     private static _424.Solution1 solution1;
+    private static _424.Solution2 solution2;
     private static String s;
     private static int k;
-    private static int actual;
     private static int expected;
 
     @BeforeClass
     public static void setup() {
         solution1 = new _424.Solution1();
+        solution2 = new _424.Solution2();
     }
 
     @Test
     public void test1() {
         s = "ABAB";
         k = 2;
-        actual = solution1.characterReplacement(s, k);
         expected = 4;
-        assertEquals(expected, actual);
+        assertEquals(expected, solution1.characterReplacement(s, k));
+        assertEquals(expected, solution2.characterReplacement(s, k));
     }
 
     @Test
     public void test2() {
         s = "AABABBA";
         k = 1;
-        actual = solution1.characterReplacement(s, k);
         expected = 4;
-        assertEquals(expected, actual);
+        assertEquals(expected, solution1.characterReplacement(s, k));
     }
 
     @Test
     public void test3() {
         s = "AAAA";
         k = 2;
-        actual = solution1.characterReplacement(s, k);
         expected = 4;
-        assertEquals(expected, actual);
+        assertEquals(expected, solution1.characterReplacement(s, k));
     }
 
     @Test
     public void test4() {
         s = "AAAB";
         k = 0;
-        actual = solution1.characterReplacement(s, k);
         expected = 3;
-        assertEquals(expected, actual);
+        assertEquals(expected, solution1.characterReplacement(s, k));
     }
 
     @Test
     public void test5() {
         s = "AABA";
         k = 0;
-        actual = solution1.characterReplacement(s, k);
         expected = 2;
-        assertEquals(expected, actual);
+        assertEquals(expected, solution1.characterReplacement(s, k));
     }
 
     @Test
     public void test6() {
         s = "ABBB";
         k = 2;
-        actual = solution1.characterReplacement(s, k);
         expected = 4;
-        assertEquals(expected, actual);
+        assertEquals(expected, solution1.characterReplacement(s, k));
     }
 }
