*The for-loop for end is executed for at most 26 times under each start. So, since we consider 26 as a constant, the loops take O(n).*

*However, thanks to @StefanPochmann, I noticed that my indexOf() takes O(n) time too, so it is O(n^2) in worst case.*

First, traverse the string to store how many times each letter has occurred from 0 to i.

Then, find the longest working substring starting at each position, with the starting point from left to right.

The key to not get TLE is to start with the longest, then (1) if the long substring does not work, cut its tail to exclude the letter that makes it not working (2) obviously, if the long substring works, no need to check its substrings shorter than it (3) [most important to get "aaaaaaa....a" test case to work] if `s.length() - start`

is already smaller than the known working longest substring, we are done.

By the way, as I have commented, I could have deleted some characters that didn't appear at all to decrease the constant.

```
public class Solution {
public int longestSubstring(String s, int k) {
if (s == null || s.length() < 1) return 0;
int[][] letters = new int[26][s.length() + 1];
for (int i = 0; i < s.length(); i++) {
for (int c = 0; c < 26; c++) {
letters[c][i+1] = letters[c][i];
}
letters[s.charAt(i) - 'a'][i+1] += 1;
}
// May also optimize by deleting letters entries with 0 at end
int longest = 0;
for (int start = 0; start < s.length(); start++) {
if (longest >= s.length() - start) return longest;
for (int end = s.length(); end > start; end--) {
boolean works = true;
for (int c = 0; c < 26; c++) {
int num = letters[c][end] - letters[c][start];
if (num < k && num > 0) {
works = false;
end = s.indexOf('a' + c, start) + 1;
break;
}
}
if (works) {
if (end - start > longest) longest = end - start;
break;
}
}
}
return longest;
}
}
```