Java 5ms Solution, with examination, easy to understand


  • 0
    F

    Based on aaaeeeo 's solution.
    https://discuss.leetcode.com/topic/70887/very-clean-and-short-7ms-java-solution-based-on-70664914-s-idea

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

Log in to reply
 

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