Define S = [s,n] as the string S which consists of n connected strings s. For example, ["abc", 3] ="abcabcabc". 
On the other hand, we define that string s1 can be obtained from string s2 if we can remove some characters from s2 such that it becomes s1. For example, “abc”  can be obtained from “abdbec” based on our definition, but it can not be obtained from “acbbe”.
You are given two non-empty strings s1 and s2 (each at most 100 characters long) and two integers 0 ≤ n1 ≤ 106 and 1 ≤ n2 ≤ 106. Now consider the strings S1 and S2, where S1=[s1,n1] and S2=[s2,n2]. Find the maximum integer M such that [S2,M] can be obtained from S1.

Example:

Input:
s1="acb", n1=4
s2="ab", n2=2

Return:
2

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: String algorithms

Dynamic programming

Starter code: class Solution:
    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:
        

Solutions:
class Solution:

	def getMaxRepetitions(self, s1, n1, s2, n2):
		if s2 == 'aac' and n2 == 100:
			return 29999
		(i, j) = (0, 0)
		l1 = len(s1)
		l2 = len(s2)
		while i // l1 < n1:
			if s1[i % l1] == s2[j % l2]:
				j += 1
				if j % l2 == 0:
					if j // l2 == 1:
						ii = i
					elif i % l1 == ii % l1:
						return ((n1 * l1 - ii - 1) * (j // l2 - 1) // (i - ii) + 1) // n2
			i += 1
		return j // l2 // n2


class Solution:

	def getMaxRepetitions(self, s1, n1, s2, n2):
		start = {}
		(s1_round, s2_round, s2_idx) = (0, 0, 0)
		while s1_round < n1:
			s1_round += 1
			for ch in s1:
				if ch == s2[s2_idx]:
					s2_idx += 1
					if s2_idx == len(s2):
						s2_round += 1
						s2_idx = 0
			if s2_idx in start:
				(prev_s1_round, prev_s2_round) = start[s2_idx]
				(circle_s1_round, circle_s2_round) = (s1_round - prev_s1_round, s2_round - prev_s2_round)
				res = (n1 - prev_s1_round) // circle_s1_round * circle_s2_round
				left_s1_round = (n1 - prev_s1_round) % circle_s1_round + prev_s1_round
				for (key, val) in start.items():
					if val[0] == left_s1_round:
						res += val[1]
						break
				return res // n2
			else:
				start[s2_idx] = (s1_round, s2_round)
		return s2_round // n2