Java 5 ms solution, similar idea from #418 Sentence Screen Fitting


  • 1
    H

    The idea is similar with #418 sentence screen fitting, e.g. store the next index

    1. At Prepare funciton, calculate for each idx in s1, the next idx for fitting exactly one s2, and how many s1 is needed
    2. Find the Looping starting index of s1, which means:
      m s1 can fit n s2, always from idx to idx at s1,
      also need to know how many times we used s1 before reaching loop index,
      and how many times we get s2 before reaching loop index
    3. Using those parameters we can calculate overall how many times we can get s2 from n1 s1
        public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
    	if (s1.length()*n1 < s2.length()*n2) return 0;
            char[] ss1 = s1.toCharArray();
            char[] ss2 = s2.toCharArray();
            for (char c: ss2) {
            	if (!s1.contains(c+"")) return 0;
            }
            int[] s1NextIdx = new int[ss1.length];
            int[] s1Costs = new int[ss1.length];
            prepare(ss1, ss2, s1NextIdx, s1Costs);
            int s1used = 0;
            int s1Idx = 0;
            int s2Count = 0;
            boolean[] used = new boolean[ss1.length];
            while (!used[s1Idx] && (s1used+s1Costs[s1Idx] <= n1)) {
                used[s1Idx] = true;
                s1used += s1Costs[s1Idx];
                s1Idx = s1NextIdx[s1Idx];
                s2Count++;
            }
            if (s1used+s1Costs[s1Idx] > n1) return s2Count/n2;
            if (s1Idx == 0 && n1%s1used == 0) {
            	return s2Count*n1/s1used/n2;
            }
            int startIdx = 0;
            int preS2Count = 0;
            int preS1Used = 0;
            
            while (startIdx != s1Idx) {
                s1used -= s1Costs[startIdx];
                preS1Used += s1Costs[startIdx];
                startIdx = s1NextIdx[startIdx];
                s2Count--;
                preS2Count++;
            }
            if (preS2Count > 0) preS1Used++;
            int times = (n1-preS1Used)/s1used;
            s2Count = s2Count*times + preS2Count;
            s1used = preS1Used + times*s1used;
            //calcualting the tail part
            while (s1used+s1Costs[s1Idx] <= n1) {
                s1used += s1Costs[s1Idx];
                s1Idx = s1NextIdx[s1Idx];
                s2Count++;
            }
            return s2Count/n2;
        }
        private void prepare(char[] s1, char[] s2, int[] s1NextIdx, int[] s1Cost) {
            boolean[] used = new boolean[s1.length];
            int idx = 0;
            while (!used[idx]) {
                used[idx] = true;
                int curr = idx;
                int count = 0;
                int s2idx = 0;
                while (s2idx < s2.length) {
                    if (s1[curr++] == s2[s2idx]) {
                        s2idx++;
                    }
                    if (curr >= s1.length) {
                        curr = 0;
                        count++;
                    }
                }
                s1Cost[idx] = count;
                s1NextIdx[idx] = curr;
                idx = curr;
            }
        }
    

Log in to reply
 

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