add 1392

fishercoder1534 · fishercoder1534 · commit c1218b3a5057 · 2020-03-22T09:48:56.000-07:00
diff --git a/README.md b/README.md
@@ -8,6 +8,7 @@ _If you like this project, please leave me a star._ &#9733;
 
 |  #  |      Title     |   Solutions   | Video  | Difficulty  | Tag                   
 |-----|----------------|---------------|--------|-------------|-------------
+|1392|[Longest Happy Prefix](https://leetcode.com/problems/longest-happy-prefix/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1392.java) | |Hard|String|
 |1390|[Four Divisors](https://leetcode.com/problems/four-divisors/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1390.java) | |Medium|Math|
 |1389|[Create Target Array in the Given Order](https://leetcode.com/problems/create-target-array-in-the-given-order/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1389.java) | |Easy|Array|
 |1388|[Pizza With 3n Slices](https://leetcode.com/problems/pizza-with-3n-slices/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1388.java) | |Hard|DP|
diff --git a/src/main/java/com/fishercoder/solutions/_1392.java b/src/main/java/com/fishercoder/solutions/_1392.java
@@ -0,0 +1,52 @@
+package com.fishercoder.solutions;
+
+/**
+ * 1392. Longest Happy Prefix
+ *
+ * A string is called a happy prefix if is a non-empty prefix which is also a suffix (excluding itself).
+ * Given a string s. Return the longest happy prefix of s .
+ * Return an empty string if no such prefix exists.
+ *
+ * Example 1:
+ * Input: s = "level"
+ * Output: "l"
+ * Explanation: s contains 4 prefix excluding itself ("l", "le", "lev", "leve"), and suffix ("l", "el", "vel", "evel"). The largest prefix which is also suffix is given by "l".
+ *
+ * Example 2:
+ * Input: s = "ababab"
+ * Output: "abab"
+ * Explanation: "abab" is the largest prefix which is also suffix. They can overlap in the original string.
+ *
+ * Example 3:
+ * Input: s = "leetcodeleet"
+ * Output: "leet"
+ *
+ * Example 4:
+ * Input: s = "a"
+ * Output: ""
+ *
+ * Constraints:
+ * 1 <= s.length <= 10^5
+ * s contains only lowercase English letters.
+ * */
+public class _1392 {
+    public static class Solution1 {
+        /**credit: https://leetcode.com/problems/longest-happy-prefix/discuss/547446/C%2B%2BJava-Incremental-Hash-and-DP*/
+        public String longestPrefix(String s) {
+            long headHash = 0;
+            long tailHash = 0;
+            long multiplier = 1;
+            long len = 0;
+            long mod = 1000000007;//use some large prime as a modulo to avoid overflow errors, e.g. 10 ^ 9 + 7.
+            for (int i = 0; i < s.length() - 1; i++) {
+                headHash = (headHash * 26 + s.charAt(i)) % mod;
+                tailHash = (multiplier * s.charAt(s.length() - i - 1) + tailHash) % mod;
+                if (headHash == tailHash) {
+                    len = i + 1;
+                }
+                multiplier = multiplier * 26 % mod;
+            }
+            return s.substring(0, (int) len);
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_1392Test.java b/src/test/java/com/fishercoder/_1392Test.java
@@ -0,0 +1,48 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._1392;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _1392Test {
+
+    private static _1392.Solution1 solution1;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _1392.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        assertEquals("l", solution1.longestPrefix("level"));
+    }
+
+    @Test
+    public void test2() {
+        assertEquals("abab", solution1.longestPrefix("ababab"));
+    }
+
+    @Test
+    public void test3() {
+        assertEquals("leet", solution1.longestPrefix("leetcodeleet"));
+    }
+
+    @Test
+    public void test4() {
+        assertEquals("", solution1.longestPrefix("a"));
+    }
+
+    @Test
+    public void test5() {
+        assertEquals("aaaa", solution1.longestPrefix("aaaaa"));
+    }
+
+    @Test
+    public void test6() {
+        assertEquals("", solution1.longestPrefix("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"));
+    }
+
+}
