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


  • 6
    A

    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;
        }
    }
    

  • 1
    F

    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;
        }
    

  • 0
    D

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


Log in to reply
 

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