If there are letters with frequency less than k. This character can not be in the longest substring. Let us use B to represent letters with frequency less than k and A for frequency larger than k.

For a string such as:

(AA...AA)B(AA...AA)B(AA...AA)

The new problem is finding longest substring in the 3 (AA...AA) part. This will be a natural recursive structure.

Now the problem is when to stop recursion.

- If your current string is already shorter than k.
- When all the letters in this substring has frequency larger than k. Then this substring is a valid candidate. we can compare it to max_len.

And for initialization, we set max_len to be k-1 since the smallest valid longest substring should be k.

```
class Solution {
public:
int longestSubstring(string s, int k) {
int ret = k-1;
longest(s, k, 0, s.size()-1, ret);
return ret == k-1 ? 0 : ret;
}
void longest(string str, int k, int s, int e, int& max_len) {
if(s > e || e-s+1 < max_len) {
return;
}
// Consider which are valid letters
vector<int> freq(26, 0);
for(int i = s; i <= e; ++i) {
freq[str[i]-'a'] += 1;
}
// when all the letters are >= k
bool satisfy = true;
for(int i = 0; i < 26; ++i) {
if(freq[i] > 0 && freq[i] < k) {
satisfy = false;
}
}
// all letters >= k
if(satisfy) {
max_len = max(e-s+1, max_len);
return;
}
// otherwise, we generate smaller piece of substrings
for(int p = s; p <= e; ){
int len = 0;
// expand as much as possible
while(p+len <= e && freq[str[p+len]-'a'] >= k) {
len += 1;
}
longest(str, k, p, p+len-1, max_len);
p += len+1;
}
}
};
```