LC-3031 Hard LeetCode

3031. Minimum Time to Revert Word to Initial State II

String Rolling Hash String Matching Hash Function

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 34% Topics: String, Rolling Hash, String Matching, Hash Function

Reading material

Strings 12 min String Matching & Hashing 13 min Arrays & Hashing 12 min

Reference solution (spoiler · python)

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

# z-function
class Solution(object):
    def minimumTimeToInitialState(self, word, k):
        """
        :type word: str
        :type k: int
        :rtype: int
        """
        def ceil_divide(a, b):
            return (a+b-1)//b
    
        def z_function(s):  # Time: O(n), Space: O(n)
            z = [0]*len(s)
            l, r = 0, 0
            for i in xrange(1, len(z)):
                if i <= r:
                    z[i] = min(r-i+1, z[i-l])
                while i+z[i] < len(z) and s[z[i]] == s[i+z[i]]:
                    z[i] += 1
                if i+z[i]-1 > r:
                    l, r = i, i+z[i]-1
            return z

        z = z_function(word)
        for i in xrange(k, len(word), k):
            if z[i] == len(word)-i:
                return i//k
        return ceil_divide(len(word), k)

Solution from kamyu104/LeetCode-Solutions · MIT