3ms C++ Solution


  • 0
    J
    class Solution {
    private:
        int dfs(string& s, int l, int r, int k, int& maxLen,int h[]) {
            int n=r-l+1;
            if (n<=maxLen)
                return maxLen;
            int hl[26]={0};
            int hr[26];
            bool flag=true;
            for (int i=0;i<26;++i) {
                hr[i]=h[i];
                if (h[i]>0 && h[i]<k)
                    flag=false;
            }
            if (flag) {
                maxLen = n;
                return n;
            }
            int i;
            for (i=l;i<=r && h[s[i]-'a']>=k;++i) {
                hl[s[i]-'a']++;
                hr[s[i]-'a']--;
            }
            hr[s[i]-'a']--;
            int left=dfs(s,l,i-1,k,maxLen,hl);
            int right=dfs(s,i+1,r,k,maxLen,hr);
            maxLen = max(left,right);
            return maxLen;
        }
    public:
        int longestSubstring(string s, int k) {
            int n=s.length();
            if (n==0)
                return 0;
            int h[26]={0};
            for (int i=0;i<n;++i)
                h[s[i]-'a']++;
            int maxLen=0;
            return dfs(s,0,n-1,k,maxLen,h);
        }
    };
    

Log in to reply
 

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