# C++ Non-recursive stack solution

• Nothing extraodinary, just use stack to avoid recursion when splitting string.
Also build and cache hash table like DP for every substring [0, i], so we don't need to re-count and re-generate the hash table again and again.

24 / 24 test cases passed
Status: Accepted
Runtime: 6 ms

``````class Solution {
public:
int longestSubstring(string s, int k) {
int siz = s.size(), max_len = 0;
stack<array<uint, 2>> stk; // each entry is a split substr(begin, len)
vector<array<uint, 26>> cnt(siz); // each element i records the counts of 26 characters within substring [0, i]
for (uint i = 0; i < siz; i++) {
if (i) memcpy(&cnt[i][0], &cnt[i-1][0], sizeof(uint)*26);
cnt[i][s[i] - 'a']++;
}
if (siz >= k) stk.push({0, siz});
while (!stk.empty()) {
uint beg = stk.top()[0], end = beg + stk.top()[1], b = beg;
stk.pop();
for (uint i = beg; i < end; i++) {
char c = s[i] - 'a';
if (cnt[end-1][c] - (b ? cnt[b-1][c] : 0) < k) {
if (i - b >= max(max_len+1, k)) stk.push({b, i-b}); // only when the substring has potential
b = i+1;
}
}
int len = end - b;
if (len > max_len) max_len = len;
}
return max_len;
}
};
``````

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