Count The Repetitions - Practice Coding Problems

Count The Repetitions - Problem

We define a string 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 = "adbec" by removing the characters 'd' and 'e'.

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.

Input & Output

Example 1 — Basic Case

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

› Output: 2

💡 Note: str1 = "acbacbacbacb". We can form str2 = "ab" twice by taking characters at positions [0,2] and [3,5], so we can get [str2, 2] from str1.

Example 2 — No Complete Match

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

› Output: 1

💡 Note: str1 = "acb" and we need s2 = "acb" once. We can form exactly 1 copy of s2 from str1.

Example 3 — Impossible Match

$ Input: s1 = "abc", n1 = 2, s2 = "def", n2 = 1

› Output: 0

💡 Note: str1 = "abcabc" contains no characters from s2 = "def", so we cannot form any copy of s2.

Constraints

1 ≤ s1.length, s2.length ≤ 100
1 ≤ n1, n2 ≤ 10⁶
s1 and s2 consist of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

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

Process

Find how many complete s2 patterns fit in str1

Output

Return min(found_matches, n2)

Key Takeaway

🎯 Key Insight: Use cycle detection to avoid simulating every character match for large repetitions

Asked in

G Google 15 M Microsoft 8

The key insight is to detect repeating patterns instead of simulating every character match. The optimal approach uses cycle detection to find when the matching state repeats, allowing us to calculate the result efficiently without building the entire concatenated string. Time: O(|s1| × |s2|), Space: O(|s1|)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Simulation	O(n1 × \|s1\| × n2 × \|s2\|)	O(n1 × \|s1\|)	Simulate matching character by character until we can't form complete s2
Pattern Detection with Cycle Finding	O(\|s1\| × \|s2\|)	O(\|s1\|)	Find repeating patterns to avoid simulating every character match

Brute Force Simulation — Algorithm Steps

Step 1: Create the full string str1 by repeating s1 n1 times
Step 2: Use two pointers to match characters of s2 against str1
Step 3: Count how many complete s2 strings we can match

Visualization

Tap to expand

Step-by-Step Walkthrough

Build str1

Create full string by repeating s1

Match s2

Scan str1 to find complete s2 patterns

Count

Return number of complete matches found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(char* s1, int n1, char* s2, int n2) {
    if (n1 == 0 || n2 == 0) {
        return 0;
    }
    
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    
    // Build the full str1
    char* str1 = malloc((len1 * n1 + 1) * sizeof(char));
    str1[0] = '\0';
    for (int i = 0; i < n1; i++) {
        strcat(str1, s1);
    }
    
    int count = 0;
    int i = 0;
    int str1Len = strlen(str1);
    
    // Try to match as many complete s2 as possible
    while (count < n2) {
        // Try to match one complete s2
        int j = 0;
        int startI = i;
        
        while (j < len2 && i < str1Len) {
            if (str1[i] == s2[j]) {
                j++;
            }
            i++;
        }
        
        // If we couldn't match complete s2, break
        if (j < len2) {
            break;
        }
            
        count++;
    }
    
    free(str1);
    return count;
}

int main() {
    char s1[101], s2[101];
    int n1, n2;
    
    fgets(s1, sizeof(s1), stdin);
    s1[strcspn(s1, "\n")] = 0;
    
    scanf("%d", &n1);
    getchar();
    
    fgets(s2, sizeof(s2), stdin);
    s2[strcspn(s2, "\n")] = 0;
    
    scanf("%d", &n2);
    
    int result = solution(s1, n1, s2, n2);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n1 × |s1| × n2 × |s2|)

Need to scan through str1 multiple times to match all possible s2 occurrences

✓ Linear Growth

Space Complexity

O(n1 × |s1|)

Store the entire concatenated string str1

⚡ Linearithmic Space

12.0K Views

Medium Frequency

~35 min Avg. Time

285 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler