24ms Java Clean Solution


  • 0
    K
    public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
        //get count of s2 in s1*n1
        int count = getCount(s1, s2, n1);
        return count/n2;
    }
    
    private int getCount(String s1, String s2, int n) {
        Map<String, Integer> map = new HashMap<String, Integer>();
        //store cumulative count of s2
        List<Integer> sums = new ArrayList<Integer>();
        String s = s1;
        int sum = 0;
        sums.add(sum);
        int i = 0;
        while (i < n) {
            //cycle caught, break
            if (map.containsKey(s))
                break;
            //count s2 in s, add sum and return suffix index
            int suffixIndex = countAndUpdateSums(sums, sum, s, s2);
            sum = sums.get(sums.size()-1);
            map.put(s, sums.size()-1);
            s = s.substring(suffixIndex) + s1;
            i++;
        }
        int result = sum;
        if (i < n) {
            int cycleCount = sum-sums.get(map.get(s)-1);
            int cycleLen = map.size()-map.get(s)+1;
            int cycleNum = (n-i)/cycleLen;
            int postCycleLen = (n-i)%cycleLen;
            int postCycleCount = sums.get(map.get(s)+postCycleLen-1)-sums.get(map.get(s)-1);
            result += cycleCount*cycleNum+postCycleCount;
        }
        return result;
    }
    
    private int countAndUpdateSums(List<Integer> sums, int sum, String s1, String s2) {
        int i = 0;
        int j = 0;
        int last = 0;
        int count = 0;
        while (i < s1.length()) {
            if (s1.charAt(i) == s2.charAt(j))
                j++;
            i++;
            if (j == s2.length()) {
                last = i;
                count++;
                j = 0;
            }
        }
        sum += count;
        sums.add(sum);
        return last;
    }

Log in to reply
 

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