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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count The Repetitions

Number: 466

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given two strings s1 and s2, along with integers n1 and n2, we form two new strings: str1 = [s1, n1] (which is s1 concatenated n1 times) and str2 = [s2, n2]. The task is to determine the maximum integer m such that the string [str2, m] (i.e., str2 concatenated m times) can be obtained as a subsequence from str1.

Key Insights

  • The problem involves matching a repeated subsequence (s2 repeated several times) within another repeated string (s1 repeated several times) by potentially skipping characters.
  • Instead of simulating the entire str1 (which may be huge), we simulate in rounds of s1 and count how many copies of s2 can be obtained.
  • Detecting cycles/repeating states helps to optimize the simulation since the state (current position in s2) might repeat after a certain number of s1 iterations, allowing us to jump forward and avoid repeated scans.
  • Use a mapping from the current index in s2 to a pair (number of s1 iterations processed, number of s2 matches found) to detect loops, then use arithmetic to compute the result for the total n1 iterations.

Space and Time Complexity

Time Complexity: O(n1 * |s1|) in the worst-case simulation, but practical performance is improved with cycle detection. Space Complexity: O(|s2|) for storing the state mapping for cycle detection.

Solution

The approach simulates the process of scanning s1 (repeated n1 times) to form s2 as a subsequence. For each full scan of s1:

  1. Iterate through s1 and try to match as many characters of s2 as possible.
  2. Track the current index in s2. When the end of s2 is reached, increment the count of s2 found and reset the index.
  3. Store the state (current index in s2) after each s1 pass. If a state repeats, it indicates a cycle. The cycle provides information on how many s1 iterations and how many s2 matches occur in one cycle.
  4. Calculate how many cycles can be skipped given the remaining s1 iterations, and then simulate any remaining iterations.
  5. Finally, the answer is the total number of s2 occurrences divided by n2 (since str2 = [s2, n2]).

The main data structures used are:

  • A dictionary (or map) to track the state (current index in s2) and corresponding counts.
  • Simple integer counters to track the number of s1 iterations processed and s2 matches found.

Code Solutions

Below are implementations in Python, JavaScript, C++, and Java with line-by-line comments.

# Python implementation for Count The Repetitions

def getMaxRepetitions(s1, n1, s2, n2):
    # Dictionary to store state when a specific index of s2 is encountered
    state_dict = {}
    s2_count = 0  # Number of times s2 has been found
    index_s2 = 0  # Current position in s2
    
    # Loop through each repetition (each block) of s1
    for count_s1 in range(1, n1 + 1):
        # Iterate over each character in s1
        for char in s1:
            # If the character matches the current character in s2
            if char == s2[index_s2]:
                index_s2 += 1
                # If we have matched all characters in s2
                if index_s2 == len(s2):
                    s2_count += 1
                    index_s2 = 0
        
        # If this state has been seen before, a cycle is detected
        if index_s2 in state_dict:
            # previous occurrence of this state
            previous_count_s1, previous_s2_count = state_dict[index_s2]
            # Number of s1 blocks in the cycle
            cycle_length = count_s1 - previous_count_s1
            # Number of s2 matches collected during one cycle
            cycle_s2_count = s2_count - previous_s2_count
            # Calculate how many cycles can be fitted in the remaining s1 blocks
            remaining_cycles = (n1 - count_s1) // cycle_length
            s2_count += remaining_cycles * cycle_s2_count
            # Process the remaining s1 blocks one by one after the cycle
            count_s1 += remaining_cycles * cycle_length
            # Finish out the process for the remaining blocks
            while count_s1 < n1:
                for char in s1:
                    if char == s2[index_s2]:
                        index_s2 += 1
                        if index_s2 == len(s2):
                            s2_count += 1
                            index_s2 = 0
                count_s1 += 1
            # Return maximum m such that [str2, m] can be obtained from str1
            return s2_count // n2
        else:
            # Store the state (current index in s2) with the current iteration info
            state_dict[index_s2] = (count_s1, s2_count)

    # If no cycle is found, directly return the result
    return s2_count // n2

# Example usage:
print(getMaxRepetitions("acb", 4, "ab", 2))  # Expected output: 2
← Back to All Questions