# Easy-understanding Java Solution with detailed explanation, 21ms!

• The key is, we just need to calculate what will remain after s1 obtains s2.

That is, `(s1, s2) -> (sRemain, matchCnt)`; for example,
`(abcd, ab) -> (cd, 1)`
`(ababa, ab) -> (a, 2)`
`(a, aaaa) -> (a, 0)`
`(aabaabaab, aba) -> (ab, 2)` as `aabaaba` exactly matches `aba` twice.

And, each time we append `s1` to the `remain string`, to make a sequence: (Using `[]` to mark the `remain string`)
`(abcd, ab): abcd -> [cd]abcd -> [cd]abcd -> [cd]abcd -> ...`
`(ababa, ab): ababa -> [a]ababa -> [a]ababa -> [a]ababa -> ...`
`(a, aaaa): a -> [a]a -> [aa]a -> [aaa]a -> a -> [a]a -> [aa]a -> ...`
`(aabaabaab, aba): aabaabaab -> [ab]aabaabaab -> [ab]aabaabaab -> ...`

Obviously, there will be a loop in the sequence, assume the length of loop is `loop`, and the length before the loop is `k`.
`(abcd, ab): loop=1, k=1`
`(a, aaaa): loop=4, k=0`
`(aabaabaab, aba): loop=1, k=1`

So, we just need to calculate `the count of each loop`, and `the count before entering the loop`, and calculate the total.

Here is the code with detailed comment, 21ms.

``````public class Solution {
public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
if (!ableToObtain(s1, s2)) return 0; // check if [s1. ∞] obtains s2
int cnt=0, k=-1;
String s=s1;
StringBuilder remainBuilder; // record `remain string`
ArrayList<String> stringList=new ArrayList<>(); // record all the `remain string`
ArrayList<Integer> countList=new ArrayList<>(); // record matching count from start to the current remain string
for (int i=0;i<=n1;i++) {
remainBuilder=new StringBuilder();
cnt+=getRemain(s, s2, remainBuilder); // get the next remain string, returns the count of matching
String remain=remainBuilder.toString();
if ((k=stringList.indexOf(remain))!=-1) break; // if there is a loop, break
stringList.add(remain); // record the remain string into arraylist
s=remain+s1; // append s1 to make a new string
}
// here, k is the beginning of the loop
if (k==-1) return cnt/n2; // if there is no loop
int countOfLoop=cnt-countList.get(k), loopLength=stringList.size()-k; // get matching count in the loop, and loop length
cnt=countList.get(k);
n1-=k;
cnt+=countOfLoop*(n1/loopLength);
n1%=loopLength;
cnt+=countList.get(k+n1)-countList.get(k);
return cnt/n2;
}

// check if [s1. ∞] obtains s2
private boolean ableToObtain(String s1, String s2) {
boolean[] cnt=new boolean[26];
for (char c: s1.toCharArray()) cnt[c-'a']=true;
for (char c: s2.toCharArray()) {
if (!cnt[c-'a']) return false;
}
return true;
}

// get remain string after s1 obtains s2, return the matching count
private int getRemain(String s1, String s2, StringBuilder remain) {
int cnt=0, lastMatch=-1, p2=0;
for (int p1=0;p1<s1.length();p1++) {
if (s1.charAt(p1)==s2.charAt(p2)) {
if (++p2==s2.length()) {
p2=0;
cnt++;
lastMatch=p1;
}
}
}
remain.append(s1.substring(lastMatch+1));
return cnt;
}
}
``````

• Brilliant! So clever!!!!!

• nice solution, I took reference of your code and tried to give more detailed explanation about how the math is done to calculate loop logic.

https://discuss.leetcode.com/topic/72525/java-solution-with-explanation

• Thanks for your brilliant idea, but there is a bug here.
// for (int i=0;i<=n1;i++) should be // for (int i = 0;i < n1; i++)
an example:
"aa"
2
"aaaaa"
1

• @ckcz123 Your solution is fundamentally brute force + optimization from loop. I rewrite the solution inspired from your idea at here: https://discuss.leetcode.com/topic/90087/java-brute-force-one-optimization-from-loop.

There is one missing piece in your argument: why is there a loop? Without loop, this solution degenerates into brute force solution.

If character_set(s1) is a superset of character_set(s2), then we know after combing at most len(s2) times of s1 together, we must find a match for s2. Possibly we don't need len(s2) times, but len(s2) is the upper bound. The first time we find a match for s2, we know the remaining string must be a suffix from s1 (because once we find a match, the last s1 must have contributed, so the remaining string must be a suffix from s1). So the remaining string only has limited number of choices. So remaining string must repeat itself after len(s1) number of matching. Hence a loop will be found.

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