Algorithm


Problem Name: 466. Count The Repetitions

We define str = [s, n] as the string str which consists of the string s concatenated n times.

  • For example, str == ["abc", 3] =="abcabcabc".

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, s1 = "abc" can be obtained from s2 = "abdbec" based on our definition by removing the bolded underlined characters.

You are given two strings s1 and s2 and two integers n1 and n2. You have the two strings str1 = [s1, n1] and str2 = [s2, n2].

Return the maximum integer m such that str = [str2, m] can be obtained from str1.

 

Example 1:

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

Example 2:

Input: s1 = "acb", n1 = 1, s2 = "acb", n2 = 1
Output: 1

 

Constraints:

  • 1 <= s1.length, s2.length <= 100
  • s1 and s2 consist of lowercase English letters.
  • 1 <= n1, n2 <= 106

Code Examples

#1 Code Example with Javascript Programming

Code - Javascript Programming


const getMaxRepetitions = function(s1, n1, s2, n2) {
  let j = 0,
    i,
    count = 0,
    perCycle = 0,
    firstEnd = -1,
    lastEnd = -1,
    nonMatch = 0
  for (i = 0; i  <  s1.length * n1; i++) {
    if (s2[j] === s1[i % s1.length]) {
      j++
      nonMatch = 0
    } else if (++nonMatch >= s1.length) break
    if (j === s2.length) {
      count++
      perCycle++
      j = 0
      if (lastEnd !== -1) continue
      else if (firstEnd === -1) {
        firstEnd = i
        perCycle = 0
      } else if ((i - firstEnd) % s1.length === 0) {
        let cycleLen = i - firstEnd
        let remainLen = s1.length * n1 - i - 1
        let cycles = Math.floor(remainLen / cycleLen)
        count += cycles * perCycle
        i += cycles * cycleLen
      }
    }
  }
  return Math.floor(count / n2)
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
s1 = "acb", n1 = 4, s2 = "ab", n2 = 2

Output

x
+
cmd
2

#2 Code Example with Python Programming

Code - Python Programming


class Solution(object):
    def getMaxRepetitions(self, s1, n1, s2, n2):
        start = {} # s2_idx : s1_round, s2_round
        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
Copy The Code & Try With Live Editor

Input

x
+
cmd
s1 = "acb", n1 = 4, s2 = "ab", n2 = 2

Output

x
+
cmd
2
Advertisements

Demonstration


Previous
#464 Leetcode Can I Win Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#467 Leetcode Unique Substrings in Wraparound String Solution in C, C++, Java, JavaScript, Python, C# Leetcode