# Very clean and short 7ms Java solution based on @70664914 's idea

• Based on idea here: https://discuss.leetcode.com/topic/70667/c-0ms-o-str1-length-str2-length
Thanks to @70664914
Added some early stop

``````public class Solution {
public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
int[] reps = new int[102];
int[] rests = new int[102];
int posRest=0, repTime=0;
int i=0, k=0;
if(n1 <= 0) return 0;
while(k==i) {
i++;
for(int j=0; j<s1.length(); j++) {
if(s2.charAt(posRest) == s1.charAt(j)) {
posRest++;
if(posRest == s2.length()) {
repTime++;
posRest=0;
}
}
}
if(i >= n1)
return repTime / n2;
for(k=0; k<i; k++){
if(posRest == rests[k])
break;
}
reps[i] = repTime;
rests[i] = posRest;
}
int interval = i-k;
int repeatCount = (n1-k) / interval;
int repeatTimes = repeatCount * (reps[i]-reps[k]);
int remainTimes = reps[(n1-k) % interval + k];
return (repeatTimes + remainTimes) / n2;
}
}
``````

• Thanks for your solution.And I made a bit progress

``````public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
if (s1 == null || s2 == null || n1 <= 0 || n2 <= 0) {
return 0;
}
HashMap<Integer, Integer> posMap = new HashMap<Integer, Integer>(); // key: the rest position of s2  value:the number of s1
int[] repTimes = new int[102]; // repTimes[i]: nummer of used s1 is i, repetitions times is repTimes[i]
char[] chars1 = s1.toCharArray();
char[] chars2 = s2.toCharArray();
int len1 = s1.length();
int len2 = s2.length();
int s1Num = 1;
int posInS2 = 0;
int times = 0;
while (s1Num <= n1) {
for (int j = 0; j < len1; j++) {
if (chars1[j] == chars2[posInS2]) {
posInS2++;
if (posInS2 == len2) {
times++;
posInS2 = 0;
}
}
}
repTimes[s1Num] = times;
if (posMap.containsKey(posInS2)) {
break;
}
posMap.put(posInS2, s1Num);
s1Num++;
}
if (s1Num >= n1) {
return times / n2;
}
int k = posMap.get(posInS2);
int s1NumInLoop = s1Num - k; // s1 num in each loop
int s2NumInLoop = repTimes[s1Num] - repTimes[k]; // s2 num in each loop
int repeatCount = (n1 - k) / s1NumInLoop;
int n = repeatCount * s2NumInLoop;
n += repTimes[k + (n1 - k) % s1NumInLoop];
return n / n2;
}
``````

• @aaaeeeo
Thank you for your code.

After I got the basic idea of the code, I just have one question: why initiate reps and rests with arrays that have the size of 102?

Please correct me if I am wrong, reps is used to store the repetition times of s2 (reps[2] = 3 means 2 s1 concatenation could produce 3 s2 concatenation) and rests is used to store the location of s2's pointer after each iteration of s1 (rests[2] = 3 means after two iterations of s1, s2's pointer has moved to the fourth character of the string). Then the length of these two arrays would have nothing to do with the length of string s1 or s2 (the maximal value would be n1).

Do you mind explain the reason behind this choice of length? I'd really appreciate it. Thank you!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.