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


  • 14
    C

    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 
            stringList.add(""); // record empty string
            countList.add(0);
            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 
                countList.add(cnt);
                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;
        }
    }
    

  • 1
    W

    Brilliant! So clever!!!!!


  • 0
    C

    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


  • 0
    F

    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


  • 0
    D

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


Log in to reply
 

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