# Java recursive solution, average O(nlogn), worst O(n^2)

• Whenever we found a character that occurs less than `k` times in the range, we know that the solution sub-string won't cross this character. So the problem can be divided into non-overlapping sub-problems.

In the average case, because we divide evenly, so `T(n) = s * T(n/s) + n` and `T(n) = O(nlogn)`; if we divide very pathologically, then `T(n) = T(n - 2) + n`, so `T(n) = O(n^2)`.

``````public class Solution {
public int longestSubstring(String s, int k) {
if (s == null || s.length() == 0) {
return 0;
}
return longestSubstring(s, k, 0, s.length() - 1);
}

private int longestSubstring(String s, int k, int bIndex, int eIndex) {
if (bIndex > eIndex) {
return 0;
}
Map<Character, Integer> count = new HashMap<>();
for (int i = bIndex; i <= eIndex; i++) {
char ch = s.charAt(i);
count.put(ch, count.containsKey(ch) ? count.get(ch) + 1 : 1);
}
int ret = -1;
int p = bIndex;
int selfLen = eIndex - bIndex + 1;
while (p <= eIndex) {
int q = p;
for (; q <= eIndex && count.get(s.charAt(q)) >= k; q++) {}
if (q - p < selfLen) {
ret = Math.max(ret, longestSubstring(s, k, p, q - 1));
}
p = q + 1;
}
return ret == -1 ? selfLen : ret;
}
}
``````

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