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

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

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