We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count The Repetitions

Difficulty: Hard

Problem Description

You are given two strings s1 and s2 and two integers n1 and n2. Define str1 = [s1, n1] and str2 = [s2, n2]. The goal is to return the maximum integer m such that str = [str2, m] can be obtained from str1, meaning we can remove some characters from str1 to form str2 repeated m times.

Key Insights

  • A string can be formed from another string by removing characters while maintaining the order.
  • To solve the problem, we need to determine how many times str2 can be formed from str1.
  • We need to consider the repetition counts of both strings.
  • The approach involves simulating the process of matching characters while considering the repetitions.

Space and Time Complexity

Time Complexity: O(n1 + n2)
Space Complexity: O(1)

Solution

The solution employs a two-pointer technique to traverse through the characters of str1 and str2. The idea is to keep track of how many times we can match the characters of str2 in str1, considering the specified repetitions. We simulate concatenating s1 by cycling through its characters, and for each character in str2, we check if it can be matched. We repeat this until we cannot match any more characters from str2.

Code Solutions

def getMaxRepetitions(s1: str, n1: int, s2: str, n2: int) -> int:
    count, i, j = 0, 0, 0
    len1, len2 = len(s1), len(s2)
    
    # Loop until we have processed all characters of s1 * n1
    while i < n1:
        for char in s1:
            if char == s2[j]:
                j += 1
                if j == len2:  # Completed one full s2
                    count += 1
                    j = 0  # Reset j to start over
        i += 1  # Move to the next repetition of s1
    
    return count // n2  # Return the maximum complete repetitions of s2
← Back to All Questions