The exact time complexity is O(26n) = O(n), where n is the length of the input string.

The proof is simply that every time, we remove a letter (all of that one) from string (or sub-string). So the maximum level of recursion tree is 26, since there are only 26 letters in this case. And at each level, the total characters we need process are no more than n. Thus, the time complexity is O(n).

Visualization:

[00000000000000000000000000] number of kinds of letters remained: no more than L (L<=26);

[000000000].....[000000]...[00000] number of kinds of letters remained no more than L-1;

...

...

...

So the total level is no more than 26;

```
public int longestSubstring(String s, int k) {
int[] map = new int[26];
for(int i=0;i<s.length();i++) {
map[s.charAt(i)-'a']++;
}
char noChar = 'a';
boolean containsNoChar = false;
for(int i=0;i<26;i++) {
noChar = (char)('a'+i);
if(map[i]<k&&map[i]!=0) {
containsNoChar = true;
break;
}
}
if(containsNoChar==false) return s.length();
int ans = 0;
int start = 0;
while(s.indexOf(noChar, start)!=-1) {
int end = s.indexOf(noChar, start);
ans = Math.max(ans, longestSubstring(s.substring(start,end), k));
start = end + 1;
}
ans = Math.max(ans, longestSubstring(s.substring(start,s.length()), k));
return ans;
}
```