2ms C++ recursive solution with explaination


  • 0
    1. First-scan: Build a local hash map to record the appearances of each character
    2. Second-scan: the character which appearances smaller than k can "split" the string into many parts(it can be more than 2 parts)
    3. do step 1~2 to the parts which was split in 2 recursively

    Recursive exit: when all local appearances is larger than k(In an other word, the string has not been split), we get a Substring with At Least K Repeating Characters just compare them to get the longest.

    class Solution {
    public:
        int longestSubstring(string s, int k) {
            maxLen=0;
            solve(s,0,s.size(),k);
            return maxLen;
        }
    private:
        int maxLen;
        void solve(string &s,int left,int right,int k){
            int dict[26]={0};
            //count
            for(int i=left;i<right;++i){
                ++dict[s[i]-'a'];
            }
            //split
            int start=left;
            for(int i=left;i<right;++i){
                if(dict[s[i]-'a']<k){
                    if(start!=i){
                        solve(s,start,i,k);
                    }
                    start=i+1;
                }
            }
            //check if is a legal substring
            if(start==left)
                maxLen=max(maxLen,right-left);
            else if(start!=right)
                solve(s,start,right,k);
            
        }
    };
    

Log in to reply
 

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