# Java Divide and Conquer + brief explanation

• The solution is to use divide and conquer approach. Lets first count how many times appears each character in the string s. Then we can use the fact that the i-th character's counter which is less than k will not exist in the answer. So, we need to divide into two parts and search the best answer from those two parts: [start, i-1] and [i+1, end].

``````public class Solution {
public int longestSubstring(String s, int k) {
if (s.length()<k) return 0;
HashMap<Character, Integer> counts = getCounts(s);
for (int i=0; i<s.length(); i++) {
if (counts.get(s.charAt(i))<k) {
int left = longestSubstring(s.substring(0, i), k);
int right = longestSubstring(s.substring(i+1), k);
return  Math.max(left, right);
}
}
return s.length();
}

private HashMap<Character, Integer> getCounts(String s) {
HashMap<Character, Integer> counts = new HashMap<>();
for (int i=0; i<s.length(); i++) {
counts.put(s.charAt(i), counts.getOrDefault(s.charAt(i), 0) +1);
}
return counts;
}
}
``````

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