# Count the repetitions

Posted: 10 Mar, 2021
Difficulty: Hard

## PROBLEM STATEMENT

#### It is defined that 'S1' can be obtained from 'S2' if we can remove some character from 'S2' to get 'S1'. For example, string 's' = ”ab” can be obtained from “adeb” but not from “adef”.

##### For example,
``````S1[“abc” 4] , S2 = [“ab” 2]

Here, 'S1' = ”abcabcabcabc” and  'S2' = ”abab”,
After deleting all ‘c’ from 'S1' becomes  S'1 = “abababab”, which can also be written as
S'1 =[“abab" 2] = [S2 2].
Hence the 'M' = 2.
``````
##### Input Format
``````The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows

The first line of each test case contains a string 's1' and an integer 'N1', where 'S1' = [s1, n1].

Second line of each test case contains a string 's2' and an integer 'N2', where 'S2' = [s2, n2].
``````
##### Output Format
``````For each test case, you have to return an integer M such that [S2,M] can be obtained from S1.
``````

#### Note:

``````You do not need to print anything or take input. This already has been taken care of. Just implement the function.
``````
##### Constraints:-
``````1 <= T <= 5
1 <= length of s1, length of s2 <= 100
1 <= n1, n2 <= 10^3

Time Limit: 1 sec
`````` Approach 1

We have to find ‘M’ such that [S2,M] is the largest subsequence. As we know ‘S2’ = [s2, N2] so we can find the number of times ‘s2’, can be obtained from ‘S1’ and then we can divide it by ‘N2’ to find the ‘M’. (number of repetitions of ‘S2’ in ‘S1’).

Algorithm:-

• Initialize a variable ‘CURRENT’ = 0 which represents the current index of ‘s2’ which we have check against ‘s1’.
• Initialize ‘OCCURRENCE’ = 0 which represents the occurrence of ‘s2’ in ‘S1’.
• Now iterate over variable ‘i’ = 0 to ‘N1 - 1’
• For each ‘i’, iterate over variable ‘j’ = 0 to s1.size()-1
• If s1[j] == s2[CURRENT] increase ‘CURRENT’.
• If CURRENT == s2.size(), set ‘CURRENT’ to zero, and increase ‘OCCURRENCE’ by 1.
• Return OCCURRENCE/N2.