# Count the repetitions

Posted: 10 Mar, 2021

Difficulty: Hard

#### A string 'S' is defined as S[s,N] such that 'N' repetitions of 's' make 'S'. For example if S[“ab” 4] then 'S' = ”abababab”. You are given two string S1[s1, N1] and S2[s2, N2]. Your task is to find the maximum value of 'M' such that [S2, M] can be obtained from S1.

#### 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.

- For each ‘i’, iterate over variable ‘j’ = 0 to s1.size()-1
- Return OCCURRENCE/N2.

Approach 2

According to the Pigeonhole principle if we have to put ‘N’ things in 'M' boxes where ‘N’ > ‘M’ then there must be more than one item in at least one box. So if N1 > N2 then there must be a repeating pattern. In this approach, we are finding the pattern then after finding the pattern we can find the occurrence for the whole string.

Algorithm:-

- Initialize 'CURRENT' = 0, which represents the current index of ‘s2’, to be compared against ‘S1’.
- Initialize ‘OCCURRENCE’ = 0 which represents the number of occurrences of ‘s2’ in ‘S1’.
- Initialize two vectors ‘CURRENTA’ & ‘OCCURRENCEA’ to store the value of ‘CURRENT’ and ‘OCCURRENCE’ for each block.
- Initialize both the vectors with zero initially.
- Iterate over ‘i’ = 0 to ‘i’ = N1-1.
- For each ‘i’ iterate from ‘j’ = 0 to s1.size()
- if(s1[j] == s2[CURRENT]) increase ‘CURRENT’ by 1.
- If ‘CURRENT’ == size of ‘s2’, change ‘CURRENT’ to 0 and OCCURRENCE++;

- Insert ‘CURRENT’ to ‘CURRENTA’ & ‘OCCURRENCE’ to ‘OCCURRENCEA’.
- Iterate from ‘k’ = 0 to ‘k’ < i-1
- If a repeating pattern is found i.e if ‘CURRENT’ = ‘CURRENTA[k]’, then we will find the number of repeating blocks, number of blocks before repetitions started and number of blocks after repetition ended. int BLOCK_BEFORE = occurence A[k], int repetitions = (occurence A[i] - OCCURRENCE[k]) * (N1 - 1 - k) / (i - k), int BLOCK_AFTER = occurence A[k + (N1 - 1 - k) %(i - k) - OCCURRENCE[k];
- Add all the three counts (BLOCK_BEFORE+ repetitions + block_after)
- Return all three counts/n2 as S2=[s2, N2].

- For each ‘i’ iterate from ‘j’ = 0 to s1.size()
- If no repetitions are found return [N1 - 1]/N2;

SIMILAR PROBLEMS

# Longest Common Prefix

Posted: 24 Jul, 2021

Difficulty: Moderate

# Maximum profit

Posted: 28 Jul, 2021

Difficulty: Moderate

# Hotel Rooms

Posted: 29 Jul, 2021

Difficulty: Moderate

# Subset OR

Posted: 31 Jul, 2021

Difficulty: Moderate

# Matching Prefix

Posted: 21 Aug, 2021

Difficulty: Moderate