Problem statement

https://leetcode.com/problems/count-the-repetitions/

Solution

Bruteforce solution is to use Two Pointers idea and to directly start to look S2 in S1, using Problem 0392 Is Subsequence. Time complexity is O(l1 * n1), where l1 is length of s1. We can do better

Let function SubStr(t, s) will return what is the longest beginning of s is subsequence of t, for example

  1. If s = abaacdbac and t = adcbd, then answer is 2, because adc is substring of s but adcb is not.
  2. Also for the case s = aaa and t = aa, answer is 3, because we can find substring and then start all over again.

We keep the following data:

  1. d is dictionary with key: number modulo l2 - what element we currently are for string s2, value is pair: how many times we traversed string s2 already; second number is how many times we traversed string s1.
  2. l is list similar to d, but in different order: l[i] means that we traversed s2 i times: first element is what element modulo l2 we are on the string s2; second number is how many times we traversed string s2.

When we traverse big string s1, each time we update pair (p, last): how many times we traversed s2 and place modulo l2. Then we check if we already have this last place in dictionary: if not, update l and d

If we already meet it, it means, that we found loop. What we need to do in this case is to calculate period T of this loop (number of times we traverse s1), C is number of times we traverse s2 on each loop and start is starting place of this loop. Then we need to find place q: the smallest element, bigger than start, which is in the same loop place as n1. Finally, we calculate how many times we need to traverse loop.

It also can happen that loop did not start and we return l[-1][1]//n2 then.

Complexity

Time complexity is O(l1 * l2), because by pigeonhole principle there will be no more than l2 elements in our d and we run function SubStr with O(l1) complexity this number of times. Space complexity is O(l2) to keep l and d.

Code

class Solution:
    def getMaxRepetitions(self, s1, n1, s2, n2):
        def SubStr(t, s):
            i, j = 0, 0
            while j < len(t):
                i, j = i + (s[i%len(s)] == t[j]), j + 1
            return i
        
        l1, l2 = len(s1), len(s2)
        d = {0: (0, 0)}
        l = [(0, 0)]
        last, p = 0, 0
        
        for i in range(1, n1 + 1):
            p, last = divmod(p*l2 + last + SubStr(s1, s2[last:]+s2[:last]), l2)
            
            if last in d:
                C, T, start = p - d[last][0], i - d[last][1], d[last][1]
                q = ((max(0, start - n1%T) - 1)//T + 1) * T + n1%T
                return (l[q][1] + (n1-q)//T*C)//n2
            
            l.append((last, p))
            d[last] = (p, i)
                       
        return l[-1][1]//n2