LC-2156 Hard LeetCode

2156. Find Substring With Given Hash Value

String Sliding Window Rolling Hash Hash Function

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 25% Topics: String, Sliding Window, Rolling Hash, Hash Function

Reading material

Strings 12 min Sliding Window 11 min String Matching & Hashing 13 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(1)

# rolling hash
class Solution(object):
    def subStrHash(self, s, power, modulo, k, hashValue):
        """
        :type s: str
        :type power: int
        :type modulo: int
        :type k: int
        :type hashValue: int
        :rtype: str
        """
        h, idx = 0, -1
        pw = pow(power, k-1, modulo)
        for i in reversed(xrange(len(s))):
            if i+k < len(s):
                h = (h-(ord(s[i+k])-ord('a')+1)*pw)%modulo
            h = (h*power+(ord(s[i])-ord('a')+1))%modulo
            if h == hashValue:
                idx = i
        return s[idx:idx+k]

Solution from kamyu104/LeetCode-Solutions · MIT