Count the repetitions

Posted: 10 Mar, 2021
Difficulty: Hard

PROBLEM STATEMENT

Try Problem

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.
  • Return OCCURRENCE/N2.
Try Problem