# C++ O(NlogN) Solution

• ``````class Solution {
vector<vector<int>> char_counts;
vector<vector<int>> char_idxs;
int solve(string & s, int l, int r, int k)
{
vector<int> split_idxs;
for (int i = 0; i < char_counts[r].size(); ++ i) ///char_counts[r].size() is constant = 26
{
int left = char_counts[l][i], right = char_counts[r][i];
if (right - left > 0 && right - left < k)
for (int j = left; j < right; ++j) /// Amortized O(1), because every idx can only be visited/added once;
split_idxs.push_back(char_idxs[i][j]);
}
if (split_idxs.empty())
return r - l;
sort(split_idxs.begin(), split_idxs.end());
int last_pos = 0, max_len = 0;
for (int i = 0; i < split_idxs.size(); ++i)
{
max_len = max(max_len, solve(s, last_pos, split_idxs[i], k));
last_pos = split_idxs[i] + 1;
}
max_len = max(max_len, solve(s, last_pos, r, k));
return max_len;
}
public:
int longestSubstring(string s, int k) {
char_idxs.resize(26);
char_counts.emplace_back(26); ///char_counts[i][c - 'a'] means counts of c BEFORE (not incl.) i
for(int i = 0; i < s.size(); ++i)
{
char_counts.push_back(char_counts.back());
char_counts.back()[s[i] - 'a'] ++;
char_idxs[s[i] - 'a'].push_back(i);
}
return solve(s, 0, s.size(), k);
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.