Problem Description

In this problem, we're given a string s and four integers named power, modulo, k, and hashValue. The objective is to find a specific substring of s of length k whose hash, calculated by a given hash function, equals hashValue. The hash function multiplies the value of each character in the substring (decided by its position in the alphabet where 'a' = 1, 'b' = 2, ..., 'z' = 26) by power raised to the index of the character, sums these products, and then takes the modulo with modulo.

More formally, for a substring of s starting at index i and ending at index i + k - 1, where 0 ≤ i ≤ len(s) - k, the hash is defined as:

(hash(s[i]) * power^0 + hash(s[i + 1]) * power^1 + ... + hash(s[i + k - 1]) * power^(k-1)) mod modulo

We must find the first such substring from the left that matches the given hashValue.

Intuition

The problem can be solved by using a sliding window technique that moves across the string from right to left. Since a straightforward approach would lead to a time complexity of O(n * k) which could be prohibitive for large strings, we need to devise a more efficient way to update the hash value as we slide the window. The algorithm uses the property that the hash of a window (substring) depends on the character leaving the window and the character entering it.

The solution relies on calculating the hash backwards, starting from the end of the string. As we move the window to the left by one character, we update the calculated hash by subtracting the value of the character that is leaving the window, multiplying the entire hash by power (to account for the positional shifts), and adding the value of the new character entering the window on the left. We take the modulo after each operation to ensure the result stays within bounds considering the modulo parameter.

Calculating power^k for each new window would be computationally expensive, so we compute it only once at the beginning, and as we move the window, we use this precomputed value to subtract the influence of the character that left the window.

The implementation uses BigInt for arithmetic operations, to handle the case where the numbers get very large. Each time when a new hash matches the given hashValue, we update the position of the answer. Once we've scanned through the string, we extract the substring from the correct position and return it. If by any chance we don't find any such substring, which shouldn't happen according to the problem statement, we'd return an empty string.

Learn more about Sliding Window patterns.

Solution Approach

The solution approach involves the use of the sliding window technique along with modular arithmetic principles to efficiently calculate and update the hash values of substrings. Let's dissect the solution code to understand its implementation:

1. The power and modulo parameters are converted to BigInt, as we will be dealing with potentially large integers due to the hash calculations and the power operations.

2. The pk variable is initialized to 1n, which represents power^k in BigInt form. This will be used later to discount the character value that is leaving the window as we slide.

3. The ac variable holds the current hash value of the windowed substring as it slides. It is also BigInt.

4. We first compute the hash value of the last k characters of the string s, since we are dealing with a reverse iteration. We multiply ac by power and add the character value of the current character using the getCode function, then take the remainder after dividing by modulo.

5. If the hash value matches hashValue at this initial position, we mark this position as ans. It is the starting index of a substring with the desired hash value.

6. Then, for each iteration moving the window one step to the left, we perform the following operations:

   • We calculate pre, which is the modular value that needs to be removed from the current hash. It represents the influence of the character that is about to leave the window.
   • Then we update ac by removing pre, and adding the new character's value, after which we multiply by power. We also need to add modulo before taking the remainder to ensure we are dealing with non-negative numbers.

7. If the newly calculated ac equals hashValue, we update ans with the current starting index of the windowed substring. Since we are iterating from right to left, the first match we find will be the first from the left in the string s.

8. The getCode helper function calculates the character value based on the alphabet index: str.charCodeAt(index) - 'a'.charCodeAt(0) + 1.

After the loop is finished, ans will hold the starting index of the correct substring or -1 if no such substring is found (as per the problem constraints, an answer always exists). We return the substring using s.substring(ans, ans + k) if a match is found; otherwise, we return an empty string.

The elegance of this approach is in the sliding window and the way we update the hash value in constant time, avoiding recomputation from scratch for each new window. This optimizes the solution and allows it to run efficiently even for large inputs.

Example Walkthrough

Let's consider a small example to illustrate the solution approach:

Suppose we have a string s = "abcde", and the integers power = 2, modulo = 100, k = 2, and hashValue = 9.

Here, the character values based on their position in the alphabet are 'a' = 1, 'b' = 2, 'c' = 3, 'd' = 4, and 'e' = 5.

The hash of a substring is calculated as follows:

(hash(s[i]) * power^0 + hash(s[i + 1]) * power^1 + ... + hash(s[i + k - 1]) * power^(k-1)) mod modulo

We want to find a substring of length k = 2 whose hash value is 9.

1. Convert power and modulo into BigInt: power = 2n and modulo = 100n.

2. The initial value of pk (which represents power^k) will be 2^2 = 4. So pk = 4n.

3. Calculate the hash value ac of the last 2 characters 'de': ac = (4 * power^0 + 5 * power^1) mod modulo = (4 + 5 * 2) mod 100 = (4 + 10) mod 100 = 14 mod 100 = 14. Since 14 is not equal to hashValue, we proceed.

4. Now slide the window to the left to compute the hash for the substring 'cd':

   • pre = hash(s[i + k - 1]) * pk mod modulo = 4 * 4 mod 100 = 16 mod 100 = 16.
   • Update ac: ac = (ac * power - pre + hash(s[i])) mod modulo = (14 * 2 - 16 + 3) mod 100 = (28 - 16 + 3) mod 100 = 15 mod 100 = 15. Again, 15 is not equal to hashValue, so we continue to move the window.

5. Next, for 'bc':

   • pre = hash(s[i + k - 1]) * pk mod modulo = 3 * 4 mod 100 = 12 mod 100 = 12.
   • Update ac: ac = (ac * power - pre + hash(s[i])) mod modulo = (15 * 2 - 12 + 2) mod 100 = (30 - 12 + 2) mod 100 = 20 mod 100 = 20. 20 does not match hashValue.

6. Lastly, check 'ab':

   • pre = hash(s[i + k - 1]) * pk mod modulo = 2 * 4 mod 100 = 8 mod 100 = 8.
   • Update ac: ac = (ac * power - pre + hash(s[i])) mod modulo = (20 * 2 - 8 + 1) mod 100 = (40 - 8 + 1) mod 100 = 33 mod 100 = 33. 33 does not match hashValue.

In this case, no substring of length 2 with the hash value of 9 can be found using the hash function described. However, this is purely an illustrative example, and according to the problem constraints, there will always be a solution.

Here, the power of the described method lies in its constant-time updates of the hash value for each sliding step, rather than recalculating from scratch. Each step involves just a few arithmetic operations, regardless of k, which makes the approach efficient for larger data.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the function subStrHash is O(n * k). Here's the breakdown:

• The first for loop runs for k iterations (where k is the length of substring we're looking for). Inside this loop, operations are constant time (with the exception of BigInt operations, which we'll assume to be O(1) for large numbers that can fit in the memory). This loop contributes O(k).
• The second for loop runs for n - k iterations where n is the length of the string s. The operations inside this loop are also constant time, thus this loop contributes O(n - k).
• Therefore, when you add both the contributions together, the worst case time complexity is O(n).

Space Complexity

The space complexity of the function subStrHash is O(1). Here's why:

• No additional data structures that grow with the input size are used. Only a fixed number of BigInt variables (ac, pk, power, modulo, hashValue) and integers (n, ans, i) are used.
• Since the algorithm doesn't utilize any space relative to the input size (ignoring the space taken by input arguments), the space complexity is constant.

Learn more about how to find time and space complexity quickly using problem constraints.