Python solution by finding cycle


  • 0
    K

    We match string s1*n1 and multiple s2 in a greedy way, trying to find a cycle. Here a cycle means that when we match s2 k times and k + cycle_length times, the last characters in both cases match to the characters of the same index in s1.
    Then s1*n1 can be decomposed into three parts: the part before the cycle, cycle part, the remaining incomplete cycle part.
    The greediness of the our matching procedure guarantee that the number of s2 matched in the first part and last part is the same as the one we would get if these two parts are concatenated, which will be a multiple of s1.

    class Solution(object):
        def getMaxRepetitions(self, s1, n1, s2, n2):
            set_s1, set_s2 = set(s1), set(s2)
            if not all(ch in set_s1 for ch in s2):
                return 0
            s1 = ''.join(ch for ch in s1 if ch in set_s2) # get rid of redundant character in s1.'
            tmap = dict()
            # tmap[i] = k means that at the first time s1[i] matchs to the last character in s2, we have matched s2 k times in total.
            record = [0]
            # record[i] = k means that k is the smallest number such that s2*i is a subsequence of s1*k.
            cnt1 = 0
            beg = 0
            while True:
                for ch in s2:
                    i = s1.find(ch, beg)
                    if i == -1:
                        cnt1 += 1
                        i = s1.find(ch)
                    beg = i+1
                record.append(cnt1 + 1)
                if record[-1] > n1:
                    return (len(record)-2)//n2
                if i in tmap: # when find a full cycle, exit the loop.
                    break
                else:
                    tmap[i] = len(record)-1
            '''
            cycle_beg denotes the number of times we have scanned s1 (including the current one) when the cycle begins.
            cycle_s1 denotes the number of s1 in a full cycle.
            cycle_s2 denotes the number of s2 in a full cycle.
            '''
            cycle_beg = record[tmap[i]]
            cycle_s1 = cnt1+1 - cycle_beg
            cycle_s2 = len(record)-1 - tmap[i]
            d, r = divmod(n1 - cycle_beg, cycle_s1)
            # d denotes the number of full cycles, r denotes the remaining number of s1 in the last incomplete cycle.
            remain = cycle_beg + r # concatenate the part before the cycle begins and the incomplete cycle remaining.
            j = 0
            while record[j] <= remain: # record[-1] > remain is yet to be proved.
                j += 1
            cnt = cycle_s2*d + j-1
            return cnt//n2
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.