o(nlogn) recursive cpp solution


  • 0
    T
    int longestSubstring(string s, int k) {
            const int SL = s.length();
            if(SL == 0) return 0;
            vector<int> chcounter(26, 0);
            for(auto ch:s) chcounter[ch-'a']++;
            int si(0), maxLen(0);
            bool allMoreK = true;
            for(int i = 0; i < SL; ++i)
                if(chcounter[s[i]-'a'] < k){
                    maxLen = max(maxLen, longestSubstring(s.substr(si, i-si), k));
                    allMoreK = false;
                    si = i+1;
                }
            return allMoreK ? SL: max(maxLen, longestSubstring(s.substr(si, SL-si), k));
        }

Log in to reply
 

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