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 = 2
Output: 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