Find Substring With Given Hash Value LeetCode solution in Java

1
class Solution {
2
  public String subStrHash(String s, int power, int modulo, int k, int hashValue) {
3
    // calculate all the powers from power^0 till power^k
4
    // utilized binary exponentiation
5
    long[] powers = new long[k];
6
    for (int i = 0; i < k; i++) powers[i] = binaryExponentiation(power, i, modulo);
7

8
    // pre compute the initial hash from behind.
9
    // I have explained at top you why traversing from behind is easy
10
    long currentHashValue = 0;
11
    int index = s.length() - 1;
12
    int powerIndex = k - 1;
13
    while (index >= s.length() - k) {
14
      // (a+b) % modulo = ( (a % modulo) + (b % modulo) ) % modulo;
15
      // do it for k times from behind
16
      currentHashValue +=
17
          ((s.charAt(index--) - 'a' + 1) % modulo * powers[powerIndex--] % modulo) % modulo;
18
    }
19
    currentHashValue %= modulo;
20

21
    int startIndex = 0;
22
    if (currentHashValue == hashValue) {
23
      startIndex = s.length() - k;
24
    }
25

26
    // I have pre computed already for k values from behind. so start from (length of S - k - 1)
27
    // Let's take an example of "leetcode" itself
28
    // "de" is pre computed
29
    // point is to add one character from behind and remove one from end (Sliding from back to
30
    // first)
31
    // Modular Arithmetic for (a-b) % modulo = ( (a % modulo) - (b % modulo) + modulo) % modulo;
32
    // keep tracking of the start index if hash value matches. That's it.
33
    for (int i = s.length() - k - 1; i >= 0; i--) {
34
      // below line a --> currentHashValue
35
      // below line b --> (s.charAt(i+k) - 'a' + 1 * powers[k-1])
36
      currentHashValue =
37
          ((currentHashValue % modulo)
38
                  - (((s.charAt(i + k) - 'a' + 1) * powers[k - 1]) % modulo)
39
                  + modulo)
40
              % modulo;
41
      // we need to multiply a power once for all
42
      // MULTIPLICATION
43
      currentHashValue = currentHashValue * power;
44
      // Modular Arithmetic for (a+b) % modulo is below line
45
      currentHashValue = (currentHashValue % modulo + (s.charAt(i) - 'a' + 1) % modulo) % modulo;
46

47
      if (currentHashValue == hashValue) {
48
        startIndex = i;
49
      }
50
    }
51
    return s.substring(startIndex, startIndex + k);
52
  }
53

54
  private long binaryExponentiation(long a, long b, long mod) {
55
    a %= mod;
56
    long result = 1;
57
    while (b > 0) {
58
      if (b % 2 == 1) result = result * a % mod;
59
      a = a * a % mod;
60
      b >>= 1;
61
    }
62
    return result;
63
  }
64
}