C++ O(NlogN) Solution


  • 0
    F
    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);
        }
    };
    

Log in to reply
 

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