466. Count The Repetitions


Problem Description

In this problem, we are working with a particular type of string operation that involves creating new strings by repeating an initial string a certain number of times. Two strings s1 and s2 and two integers n1 and n2 are given. We create two new strings:

  • str1 by repeating s1 exactly n1 times (i.e., str1 = s1 * n1).
  • str2 by repeating s2 exactly n2 times (i.e., str2 = s2 * n2).

Our task is to determine the maximum number of times (m) we can repeat str2 to obtain a string that can be derived from str1 by possibly removing some characters from str1 without rearranging the remaining characters.

For example, "abc" can be derived from "abdbc" by removing the characters "d" and "b" and by keeping the order of the remaining characters the same.

Intuition

The intuition behind the solution lies in finding how many times one instance of s2 can be formed by selectively dropping characters from s1 during its repeated concatenation to form str1. By analyzing the patterns of how s2 can be formed from s1, the solution leverages the fact that after a certain number of iterations, these patterns will repeat. Thus, rather than simulating the entire construction of str1 and then str2, we can use this pattern repetition to estimate the final result more efficiently.

The approach to solve this problem is:

  1. Construct a dictionary (d) that, for each possible start index in s2, stores how many complete s2 strings can be formed from s1 and the index at which the next s2 will start forming.
  2. Loop through n1 times (the number of times s1 is repeated), each time using the dictionary to avoid completely recomputing how many times s2 can be formed, and keeping track of the current position in s2.
  3. Aggregate the counts from each s1 repetition to get the total number of times s2 can be formed, and finally, divide that by n2 to get the maximum m that satisfies the condition.

By avoiding the unnecessary full simulation of constructing str1 and str2, the algorithm significantly reduces the time complexity from what would be prohibitive to a more manageable level, enabling it to handle large inputs efficiently.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution’s core idea is to find a repetitive pattern when matching s2 within the repeated string s1. The same sequence of matches and omissions will eventually repeat since the strings s1 and s2 are finite. This pattern can be captured and used to extrapolate the matches without explicitly iterating through each concatenation of s1.

Here's a step-by-step breakdown of the implementation:

Step 1: Constructing the Dictionary for Pattern Recognition

A dictionary d is built where each key represents a starting index in s2, and the value is a tuple consisting of two elements (cnt, j). Here, cnt is the count of how many times s2 can be formed from s1 when s2 starts from that particular index, and j is the index at which we can continue matching the next s2 after one iteration of s1.

This is done by iterating through each index i of s2 and then iterating through s1. If the current character of s1 matches the character at index j of s2, j is incremented. If j reaches the length of s2, it means s2 has been formed once, so cnt is incremented, and j is reset to 0. This process continues through the length of s1.

Step 2: Counting s2 Formations within str1

We then iterate n1 times (representing the number of s1 repetitions) and track the total count of s2 formations. In each iteration, using the current index j (which tells us where in s2 we are), we update the total count with the count stored in the dictionary and update j to the next starting index for s2 from the value associated with the current index in the dictionary.

Step 3: Calculating the Final Answer

After looping through n1 times, the total count represents how many times s2 is formed in str1. The last step is to find how many times str2 (which is s2 repeated n2 times) can be formed. This is simply the integer division of the total count by n2.

This process allows us to simulate the matching between s1 and s2 over large strings efficiently. The crucial insight is leveraging the pattern repetition and dictionary-based tracking to skip over repeated calculations, thus optimizing the process.

The solution makes use of algorithmic techniques such as greedy matching and pattern searching, and it uses a dictionary to store intermediate results for dynamic programming-like reuse. By identifying the repetitive sequences ahead of time, it circumvents the requirement of a more brute-force approach that would involve constructing and comparing the long strings str1 and str2 explicitly.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's go through an example to illustrate the solution approach with the strings s1 = "ab" and s2 = "baba" and the integers n1 = 6 and n2 = 2.

Step 1: Constructing the Dictionary for Pattern Recognition

We start by creating the dictionary d. We will iterate s1 and see how s2 fits within it:

  • Start with s2 at index 0:
    • s1[0] = 'a' does not match s2[0] = 'b', so we skip.
    • s1[1] = 'b' matches s2[0] = 'b', so we move to s2[1].
  • s1 ends, so we start again from s1[0], but now for s2[1].
    • s1[0] = 'a' matches s2[1] = 'a', so we move to s2[2].
    • s1[1] = 'b' matches s2[2] = 'b', so we move to s2[3].

One full iteration of s1 helps us reach index 3 of s2. We need to continue from here in the next cycle.

We can see that after the first s1, we can't completely form s2, but we've made some progress. Our dictionary after processing s1 once will look like this: d = {0: (0, 2)}. It tells us that starting from index 0 of s2, we can build up to index 2 with one s1.

Step 2: Counting s2 Formations within str1

Now, we would iterate over n1 times. However, since our s1 length is 2, and s2 is 4, it's clear we cannot form a single s2 fully after one iteration of s1. But for demonstration, let's loop n1=6 times and assume that one s2 can be formed after two s1 iterations. Using this example, we will operate with hypothesized values, where we assume after two iterations of s1, one s2 is formed.

With d built, we would now loop through s1 n1 times and keep a count of how many s2s we've fully formed. Assume at every two s1 iterations, we form one s2, and so after six s1 repetitions, the count would be 3.

Step 3: Calculating the Final Answer

Now, we simply calculate m = count / n2. Here, count = 3 and n2 = 2. Therefore, m = 3 / 2 = 1.

By this calculation, we determine that str2 can be formed from str1 a maximum of 1 time. In our example, because of the mismatching lengths and inability to form even one full s2, the actual calculation gave us 0 times, but through the hypothesized process, we've illustrated the algorithm's steps.

Note that for the purpose of this walkthrough, the dictionary size is only kept minimal to illustrate the concept. In practice, the dictionary d will be of size len(s2) as we have to check for each index of s2. Moreover, we assumed a simplified case where complete formation of s2 was hypothetically straight-forward to help understand the steps involved in the general case; however, the actual approach would calculate the dictionary values based on how elements of s1 map onto s2 with potentially partial formations involved.

Solution Implementation

1class Solution:
2    def getMaxRepetitions(self, source_str: str, source_count: int, target_str: str, target_count: int) -> int:
3        target_len = len(target_str)  # Length of target_str
4        repetition_dict = {}  # Dictionary to store the repetitions for each starting index of target_str
5      
6        # Build the dictionary with repetitions and the next index for each starting index in target_str
7        for idx in range(target_len):
8            count_repetitions = 0  # Counter for occurrences of target_str in source_str
9            source_idx = idx  # The current index in target_str being searched in source_str
10          
11            # Loop through each character in source_str to find repetitions of target_str
12            for char in source_str:
13                if char == target_str[source_idx]:
14                    source_idx += 1  # Move to the next index in target_str
15                if source_idx == target_len:  # When one occurrence of target_str is found
16                    count_repetitions += 1  # Increment the count
17                    source_idx = 0  # Reset the index in target_str for another search
18          
19            # Store the count of repetitions and the next search start index in the dictionary
20            repetition_dict[idx] = (count_repetitions, source_idx)
21      
22        # The variable to store the total number of repetitions of target_str in the concatenated source_str
23        total_repetitions = 0  
24        index_to_search = 0  # The starting index in target_str for the next search
25      
26        # Loop for concatenating source_str source_count times
27        for _ in range(source_count):
28            # Get the number of repetitions and the next search starting index from the dictionary
29            count_repetitions, index_to_search = repetition_dict[index_to_search]
30            total_repetitions += count_repetitions  # Update the total repetitions of target_str
31      
32        # Return the total repetitions of target_str divided by target_count to find how many full target_str can be formed
33        return total_repetitions // target_count
34
1class Solution {
2    public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
3        // Lengths of s1 and s2
4        int s1Length = s1.length(), s2Length = s2.length();
5      
6        // Create an array to store the dp result for substrings of s2
7        int[][] dp = new int[s2Length][];
8      
9        // Precompute how many times s2 can be found in s1 for each starting index
10        for (int i = 0; i < s2Length; ++i) {
11            int j = i; // Pointer for s2
12            int countInS1 = 0; // Count of s2 in s1
13          
14            // Scan s1 to see how many times the characters of s2 appear in sequence
15            for (int k = 0; k < s1Length; ++k) {
16                if (s1.charAt(k) == s2.charAt(j)) {
17                    // Move to the next character in s2
18                    j++;
19                  
20                    // If we reach the end of s2, wrap around and increment count
21                    if (j == s2Length) {
22                        j = 0;
23                        countInS1++;
24                    }
25                }
26            }
27          
28            // Store the count and next index in the dp table
29            dp[i] = new int[] {countInS1, j};
30        }
31      
32        // Main computation of max repetitions
33        int repetitions = 0;
34        int j = 0; // Initialize index for s2
35      
36        // Multiply s1 n1 times to see how many s2's can be found
37        for (; n1 > 0; n1--) {
38            // Add number of times s2 is found in this segment of s1
39            repetitions += dp[j][0];
40            // Move to the next starting index in s2
41            j = dp[j][1];
42        }
43      
44        // Return the total count found divided by n2, to see how many s2*n2 are in s1*n1
45        return repetitions / n2;
46    }
47}
48
1class Solution {
2public:
3    int getMaxRepetitions(string s1, int n1, string s2, int n2) {
4        int s1Length = s1.size(), s2Length = s2.size();
5        vector<pair<int, int>> countIndexPairs;
6      
7        // Pre-processing: Calculate how many full s2 are in one s1, for each starting position in s2
8        for (int startIndexS2 = 0; startIndexS2 < s2Length; ++startIndexS2) {
9            int currentIndexS2 = startIndexS2;
10            int countS2InS1 = 0;
11            for (int i = 0; i < s1Length; ++i) {
12                if (s1[i] == s2[currentIndexS2]) {
13                    currentIndexS2++;
14                    // If the end of s2 is reached, count it and reset the index
15                    if (currentIndexS2 == s2Length) {
16                        countS2InS1++;
17                        currentIndexS2 = 0;
18                    }
19                }
20            }
21            // Store the count of s2 in s1 and the next starting index for s2
22            countIndexPairs.emplace_back(countS2InS1, currentIndexS2);
23        }
24      
25        int totalS2Count = 0;
26        int currentStartIndexS2 = 0;
27      
28        // Main calculation: Find the total number of s2 given n1 repetitions of s1
29        while (n1 > 0) {
30            // Add the number of full s2s that correspond to the current starting index
31            totalS2Count += countIndexPairs[currentStartIndexS2].first;
32            // Move the start index to the next position based on the pre-processed data
33            currentStartIndexS2 = countIndexPairs[currentStartIndexS2].second;
34            // One s1 is used up
35            n1--;
36        }
37      
38        // We have the total number of s2s in n1 s1s. Divide by n2 to get the answer.
39        return totalS2Count / n2;
40    }
41};
42
1function getMaxRepetitions(s1: string, n1: number, s2: string, n2: number): number {
2    // `s2Length` is the length of string `s2`
3    const s2Length = s2.length;
4
5    // `repetitionInfo` holds the count of repetitions and the next index for each character in `s2`
6    const repetitionInfo: number[][] = new Array(s2Length).fill(0).map(() => new Array(2).fill(0));
7
8    // Precompute the count of `s2` in `s1` and the next starting index in `s2`
9    for (let index = 0; index < s2Length; ++index) {
10        let currentS2Index = index; // Start from the character at `index` in `s2`
11        let repetitionCount = 0; // Store the number of `s2` found in `s1`
12        for (const char of s1) {
13            if (char === s2[currentS2Index]) {
14                // If chars match, move to the next char in `s2`
15                if (++currentS2Index === s2Length) {
16                    // If at the end of `s2`, reset to beginning of `s2` and increment `repetitionCount`
17                    currentS2Index = 0;
18                    ++repetitionCount;
19                }
20            }
21        }
22        // Update precomputed info for this index
23        repetitionInfo[index] = [repetitionCount, currentS2Index];
24    }
25
26    let totalRepetitions = 0; // Store total repetitions of `s2` in `s1` * `n1`
27    for (let currentS2Index = 0; n1 > 0; --n1) {
28        // Add repetitions for current cycle of `n1`
29        totalRepetitions += repetitionInfo[currentS2Index][0];
30        // Update the index in `s2` where the next cycle will begin
31        currentS2Index = repetitionInfo[currentS2Index][1];
32    }
33
34    // Return the maximum number of `s2` repetitions in `s1` * `n1` over `n2`
35    return Math.floor(totalRepetitions / n2);
36}
37

Time and Space Complexity

Time Complexity

The provided code consists of two major parts: creating a dictionary d and calculating the answer ans.

  1. Building the dictionary d involves a nested loop where the outer loop runs for the length of s2 and the inner loop for the length of s1. The inner loop goes through s1 to count how many times s2 fits in it starting at different indices. This results in a time complexity of O(len(s1) * len(s2)) for this part, because for every character in s2, we potentially traverse s1 completely.

  2. The next part of the code loops n1 times, where each loop involves a constant time dictionary lookup and addition operation. Thus, the time complexity for this part is O(n1).

Combining these two parts, the total time complexity is O(len(s1) * len(s2) + n1).

Space Complexity

The space complexity is determined by the additional space used by our algorithm, which in this case is primarily the dictionary d:

  1. The dictionary d stores a tuple for each character of s2, so it will contain len(s2) tuples. Each tuple contains two integers, resulting in a space complexity of O(len(s2)).

  2. Apart from the dictionary, only constant extra space is used for variables ans and j.

Therefore, the total space complexity is O(len(s2)).

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which of the following is a good use case for backtracking?


Recommended Readings

Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄