add 2156

fishercoder1534 · fishercoder1534 · commit c6404c5fd824 · 2022-01-30T11:31:15.000-08: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                  
 |-----|----------------|---------------|--------|-------------|-------------
+|2156|[Find Substring With Given Hash Value](https://leetcode.com/problems/find-substring-with-given-hash-value/)|[Java](../master/src/main/java/com/fishercoder/solutions/_2156.java) ||Medium||
 |2155|[All Divisions With the Highest Score of a Binary Array](https://leetcode.com/problems/all-divisions-with-the-highest-score-of-a-binary-array/)|[Java](../master/src/main/java/com/fishercoder/solutions/_2155.java) ||Medium||
 |2154|[Keep Multiplying Found Values by Two](https://leetcode.com/problems/keep-multiplying-found-values-by-two/)|[Java](../master/src/main/java/com/fishercoder/solutions/_2154.java) ||Easy||
 |2150|[Find All Lonely Numbers in the Array](https://leetcode.com/problems/find-all-lonely-numbers-in-the-array/)|[Java](../master/src/main/java/com/fishercoder/solutions/_2150.java) ||Medium||
diff --git a/src/main/java/com/fishercoder/solutions/_2156.java b/src/main/java/com/fishercoder/solutions/_2156.java
@@ -0,0 +1,48 @@
+package com.fishercoder.solutions;
+
+public class _2156 {
+    public static class Solution1 {
+        /**
+         * Credit: https://leetcode.com/problems/find-substring-with-given-hash-value/discuss/1730100/Java-rolling-hash(back-to-front)/1242659
+         * <p>
+         * We start from the right side and compute rolling hash when moving the window of size k towards the left.
+         */
+        public String subStrHash(String s, int power, int modulo, int k, int hashValue) {
+            long weight = 1;
+            for (int j = 0; j < k - 1; j++) {
+                // calculate the weight which will be the power to the k-1
+                // this will be used when we start shifting our window of size k to the left from the end of the string
+                weight = (weight * power) % modulo;
+            }
+            /**We'll have to use the above for loop to calculate weight instead of using Math.pow(power, k - 1) which will render wrong results when power and k are big enough.*/
+
+            // initialize the result string to empty string and keep updating it as we start from the end of the string, and we need to find the first substring that has the hashvalue
+            String result = "";
+
+            // right bound of the sliding window which starts at the end of the string
+            int right = s.length() - 1;
+
+            long hash = 0;
+            for (int i = s.length() - 1; i >= 0; i--) {
+
+                // add the next value of char for the left pointer into the sliding window
+                int val = s.charAt(i) - 'a' + 1;
+
+                // update the current hash value
+                hash = (hash * power % modulo + val) % modulo;
+
+                // when window is at size k, we need to check if we find a matching hash value
+                // and update the result, and remove the right most char out of the window to prepare for next iteration
+                if (right - i + 1 == k) {
+                    if (hash == hashValue) {
+                        result = s.substring(i, right + 1);
+                    }
+                    hash = (hash + modulo - (s.charAt(right--) - 'a' + 1) * weight % modulo) % modulo;
+                }
+            }
+
+            return result;
+        }
+
+    }
+}
diff --git a/src/test/java/com/fishercoder/_2156Test.java b/src/test/java/com/fishercoder/_2156Test.java
@@ -0,0 +1,58 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._2156;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _2156Test {
+    private static _2156.Solution1 solution1;
+    private static String s;
+    private int power;
+    private int modulo;
+    private static int k;
+    private static int hashValue;
+    private static String expected;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _2156.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        s = "leetcode";
+        power = 7;
+        modulo = 20;
+        k = 2;
+        hashValue = 0;
+        expected = "ee";
+        assertEquals(expected, solution1.subStrHash(s, power, modulo, k, hashValue));
+    }
+
+    @Test
+    public void test2() {
+        s = "fbxzaad";
+        power = 31;
+        modulo = 100;
+        k = 3;
+        hashValue = 32;
+        expected = "fbx";
+        assertEquals(expected, solution1.subStrHash(s, power, modulo, k, hashValue));
+    }
+
+    @Test
+    public void test3() {
+        s = "xmmhdakfursinye";
+        power = 96;
+        modulo = 45;
+        k = 15;
+        hashValue = 21;
+        expected = "xmmhdakfursinye";
+        System.out.println(Math.pow(power, k - 1));
+        System.out.println(Math.pow(power, k - 1) % modulo);
+        assertEquals(expected, solution1.subStrHash(s, power, modulo, k, hashValue));
+    }
+
+}
