add a solution for 5

fishercoder1534 · fishercoder1534 · commit 4b094855a22f · 2021-10-21T15:14:38.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_5.java b/src/main/java/com/fishercoder/solutions/_5.java
@@ -30,4 +30,36 @@ private void extendPalindrome(String s, int left, int right) {
             }
         }
     }
+
+    public static class Solution2 {
+        /**
+         * Same sliding window idea, but without using global variables.
+         * Credit: https://leetcode.com/problems/longest-palindromic-substring/solution/
+         */
+        public String longestPalindrome(String s) {
+            int start = 0;
+            int end = 0;
+            for (int i = 0; i < s.length(); i++) {
+                int len1 = expand(s, i, i);
+                int len2 = expand(s, i, i + 1);
+                int len = Math.max(len1, len2);
+                if (len > end - start) {
+                    start = i - (len - 1) / 2;
+                    end = i + len / 2;
+                }
+            }
+            return s.substring(start, end + 1);
+        }
+
+        private int expand(String s, int left, int right) {
+            int l = left;
+            int r = right;
+            while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
+                l--;
+                r++;
+            }
+            return r - l - 1;
+        }
+
+    }
 }
diff --git a/src/test/java/com/fishercoder/_5Test.java b/src/test/java/com/fishercoder/_5Test.java
@@ -8,15 +8,22 @@
 
 public class _5Test {
     private static _5.Solution1 solution1;
+    private static _5.Solution2 solution2;
+    private static String s;
+    private static String expected;
 
     @BeforeClass
     public static void setup() {
         solution1 = new _5.Solution1();
+        solution2 = new _5.Solution2();
     }
 
     @Test
     public void test1() {
-        assertEquals("bab", solution1.longestPalindrome("babad"));
+        s = "babad";
+        expected = "bab";
+        assertEquals(expected, solution1.longestPalindrome(s));
+        assertEquals(expected, solution2.longestPalindrome(s));
     }
 
 }
