Last Updated: 10 Mar, 2021

Count the repetitions

Hard

Asked in companies

Solve now

Problem statement

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

Solve now

Approaches

01 Approach

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.

Solve now

02 Approach

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].
If no repetitions are found return [N1 - 1]/N2;

Solve now