C++ Non-recursive stack solution


  • 0
    A

    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;
        }
    };
    

Log in to reply
 

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