Exactly, it is O(26 * n) = O(n), as we only have 26 unique characters.

Precomputed the appear times and last appear position of each character, so we only need O(1) time to get the appear times and separate position for specific substring.

Each char in the string would be at most used once when separating, so the getLongestSubstr() would be called at most O(4*n) = O(n) times. As a result, it's strictly O(n).

Thanks to @StefanPochmann . The idea of his code is very neat. I just try to optimize the time complexity by precomputing.

```
class Solution {
private:
int getLongestSubstr(int l, int r, int k, vector<vector<int>> &count, vector<vector<int>> &preLoc) {
if(l > r) return 0;
for(int i = 0; i < 26; i++) {
int tot = count[i][r] - count[i][l - 1];
if(tot > 0 && tot < k) {
return max(getLongestSubstr(l, preLoc[i][r] - 1, k, count, preLoc)
,getLongestSubstr(preLoc[i][r] + 1, r, k, count, preLoc));
}
}
return r - l + 1;
}
public:
int longestSubstring(string s, int k) {
vector<vector<int>> count(26,vector<int>(s.size() + 1, 0));
vector<vector<int>> preLoc(26,vector<int>(s.size() + 1, -1));
for(int i = 0; i < 26; i++) {
char c = 'a' + i;
count[i][0] = 0;
for(int j = 0; j < s.size(); j++) {
count[i][j + 1] = count[i][j] + (s[j] == c);
preLoc[i][j + 1] = s[j] == c ? j + 1 : preLoc[i][j];
}
}
return getLongestSubstr(1, s.size(), k, count, preLoc);
}
};
```