Count the repetitions

Hard
0/120
Average time to solve is 25m
profile
Contributed by
6 upvotes
Asked in companies
MicrosoftProtivitiApple

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample input 1
2
abc 4
ab 2
abcde 5
a 3
Sample Output 1
 2
 1
Sample input explanation
Test case 1: 
Here S1 = "abcabcabcabc" and S2 = "abab"
We can obtain "abababab" from S1, which is "abab" + "abab" so M = 2.

Test case 2:
Here S1 = "abcdeabcdeabcdeabcdeabcde" and S2 = "aaa".
We can obtain "aaaaa" from S1. Here we can find S2 only one time, so M = 1.
Sample input 2
2
abcd 4
aba 2
abde 2
abde 4
Sample output 2
1
0
Hint

Check the number of times s2 repeats in S1.

Approaches (2)
Brute force

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.
Time Complexity

O(N1 * |s1|), where ‘N1’ is the number of repetitions required to convert ‘s1’ into ‘S1’, and |s1| is the length of ‘s1’.

 

As we are iterating string ‘s1’, ‘N1’ times so complexity is O(N1 * |s1|).

Space Complexity

O(1).

 

No extra space is used.

Code Solution
(100% EXP penalty)
Count the repetitions
Full screen
Console