# Java D & C Solution

• The idea is pretty basic, find the point where we should split the string, eg, the position of character which total count is <k, then dfs it then find the max.
For Example: bbcddefegaghfh and 2, so we shall dfs on "bb", "ddefeg", "ghfh", since a , c only appears1 for once.

``````public int longestSubstring(String s, int k) {
if (s == null || s.length() == 0 || k == 0) return 0;
int max = 0;
int[] count = new int[26];
int res = 0;
for (int i = 0; i < s.length(); i++) {
count[s.charAt(i) - 'a']++;
}
List<Integer> pos = new ArrayList<Integer>();
for (int i = 0; i < s.length(); i++) {
if (count[s.charAt(i) - 'a'] < k) pos.add(i);
}
if (pos.size() == 0) return s.length();
for (int i = 1; i < pos.size(); i++) {
int start = pos.get(i-1) + 1;
int end = pos.get(i);
int next = longestSubstring(s.substring(start, end), k);
res = Math.max(res, next);
}
return res;
}
``````

• @curt Can you explain me the time complexity of this algorithm?

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