This page explains Java solution to problem `Count The Repetitions`

using `String`

data structure.

Define `S = [s,n]`

as the string `S`

which consists of `n`

connected strings `s`

. For example, `["abc", 3] ="abcabcabc"`

.

On the other hand, we define that string `s1`

can be obtained from string `s2`

if we can remove some characters from `s2`

such that it becomes `s1`

. For example, `abc`

can be obtained from `abdbec`

based on our definition, but it can not be obtained from `acbbe`

.

You are given two non-empty strings `s1`

and `s2`

(each at most `100`

characters long) and two integers `0 ≤ n1 ≤ 106`

and `1 ≤ n2 ≤ 106`

. Now consider the strings `S1`

and `S2`

, where `S1=[s1,n1]`

and `S2=[s2,n2]`

. Find the maximum integer `M`

such that `[S2,M]`

can be obtained from `S1`

.

Input:

s1 = "acb", n1 = 4

s2 = "ab", n2 = 2Output: 2

```
package com.vc.hard;
import java.util.*;
class CountTheRepetitions {
public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
if(s1 == null || s2 == null || n1 <= 0 && n2 <= 0) {
return 0;
}
//Key: Position of S2
//Value: Number of times S1 is used
HashMap<Integer, Integer> loopMap = new HashMap<>();
//Key: Number of times S1 is used
//Value: Number of times S2 appears
HashMap<Integer, Integer> repMap = new HashMap<>();
int s2Count = 0, s1Count = 1, s2Index = 0;
while (s1Count <= n1) {
for(int s1Index = 0; s1Index < s1.length(); s1Index++) {
if(s1.charAt(s1Index) == s2.charAt(s2Index)) {
s2Index++;
if(s2Index == s2.length()) {
s2Count++;
s2Index = 0;
}
}
}
repMap.put(s1Count, s2Count);
if(loopMap.containsKey(s2Index)) {
break;
}
loopMap.put(s2Index, s1Count);
s1Count++;
}
if(s1Count >= n1) return s2Count / n2;
int s1CountStartOfLoop = loopMap.get(s2Index);
int s1CountInLoop = s1Count - s1CountStartOfLoop;
int s2CountInLoop = repMap.get(s1Count) - repMap.get(s1CountStartOfLoop);
//S2 Count Within a loop
int repeatCount = (n1 - s1CountStartOfLoop) / s1CountInLoop; //How many loops of s1 are possible with n1 as higher limit
int res = repeatCount * s2CountInLoop;
//S2 Count Outside of a loop
res += repMap.get(s1CountStartOfLoop + (n1 - s1CountStartOfLoop) % s1CountInLoop);
return res / n2;
}
}
```

O(len1 * len2) Where

len1 is length of input string s1

len2 is length of input string s2

O(len2 + N1) Where

N1 number of times input string s1 can be used

len2 is length of input string s2