Given a string s, find out all chars that are invalid (i.e., count < k). The longest substring must reside in one of the substrings divided by those invalid chars. We find out all those possible substrings and recursively address each of them.

NOTE: repeatedly using s.charAt() is actually very slow. If we use charAt() in the following code, the runtime becomes 6ms, doubled!

Here is the code:

```
public class Solution {
public int longestSubstring(String s, int k) {
return longestSubstringRecur(s,k);
}
public int longestSubstringRecur(String s, int k){
if (s.length()<k) return 0;
char[] charArr = s.toCharArray();
int[] charCounts = new int[26];
for (char c : charArr){
charCounts[c-'a']++;
}
// Early termination:
// 1. invalid: no char in s appears >= k times.
// Or 2. Good enough: every char appears >= k times.
boolean valid = false, goodEnough = true;
for (int count : charCounts){
if (count>=k){
valid = true;
}
if (count>0 && count <k){
goodEnough = false;
}
if (valid && !goodEnough) break;
}
if (!valid) return 0;
if (goodEnough) return s.length();
// Address every possible substring, i.e., substring between two invalid chars.
int p1=0, p2=-1, maxLen=0;
while (p1<s.length()){
p2++;
while (p2<s.length() && charCounts[charArr[p2]-'a']>=k) p2++;
int curMaxLen = longestSubstringRecur(s.substring(p1,p2),k);
maxLen = Math.max(maxLen,curMaxLen);
p1 = p2+1;
}
return maxLen;
}
}
```