My version of C++ divide solution


  • 0
    F
    class Solution {
    public:
        int longestSubstring(string s, int k) {
            return getLongest(s, 0, s.size()-1, k);
        }
    
    private:    
        int getLongest(string &s, int start, int stop, int k){
            if(start>stop) return 0;
            
            int hash[256] = {0};
            int maxAvail = 0; // Used to bail early if not possible
            for(int i = start; i <= stop; ++i){
                hash[s[i]]++;
                maxAvail = max(maxAvail, hash[s[i]]);
            }
            if(maxAvail < k) return 0;
            int splitPoint = getSplitIndex(s, start, stop, hash, k);
            if(splitPoint < 0) return stop-start+1;
            return max(getLongest(s, start, splitPoint-1, k), getLongest(s, splitPoint+1, stop, k));
        }
        int getSplitIndex(string &s, int start, int stop, int *hash, int k){
            for(int i = start; i <= stop; ++i){
                if(hash[s[i]] < k){
                    return i;
                }
            }
            return -1;        
        }
    };
    

Log in to reply
 

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