Java divide and conquer with preCount enhancement (10 times faster)


  • 0
    J

    This is a divide and conquer solution similar to the original post: https://discuss.leetcode.com/topic/57372/java-divide-and-conquer-recursion-solution. With the preCount enhancement, most of the duplicate computation is eliminated. Runtime is roughly 10 times faster (8ms vs 90ms)

    public class Solution {
        private int[][] preCount;
        public int longestSubstring(String s, int k) {
            char[] arr = s.toCharArray();
            preCount = new int[26][arr.length + 1];
            for (int i = 1; i <= arr.length; i++) {
                for (int j = 0; j < 26; j++) {
                    preCount[j][i] = preCount[j][i - 1];
                }
                preCount[arr[i - 1] - 'a'][i]++;
            } // pre calculate the counts of each character in different range
            return findLongest(arr, 0, s.length() - 1, k);
        }
        private int findLongest(char[] s, int start, int end, int k) {
            if (start > end) return 0;
            boolean[] invalids = new boolean[26];
            boolean isValid = true;
            for (int i = 0; i < 26; i++) {
                // utilize the preCount array to quickly get the count (O(1) instead of O(n))
                int count = preCount[i][end + 1] - preCount[i][start]; 
                if (count != 0 && count < k) {
                    invalids[i] = true;
                    isValid = false;
                }
            }
            if (isValid) {
                return end - start + 1;
            }
            int p = start;
            int max = Integer.MIN_VALUE;
            for (int i = start; i <= end + 1; i++) {
                if (i == end + 1 || invalids[s[i] - 'a']) {
                    max = Math.max(max, findLongest(s, p, i - 1, k));
                    p = i + 1;
                }
            }
            return max;
        }
    }
    

Log in to reply
 

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