# Count The Repetitions

This page explains Java solution to problem `Count The Repetitions` using `String` data structure.

## Problem Statement

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

Example 1:

Input:
s1 = "acb", n1 = 4
s2 = "ab", n2 = 2
Output: 2

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
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;
}
}
``````

## Time Complexity

O(len1 * len2) Where
len1 is length of input string s1
len2 is length of input string s2

## Space Complexity

O(len2 + N1) Where
N1 number of times input string s1 can be used
len2 is length of input string s2