ruby solution by Divide&Conquer


  • 0
    D
    def longest_substring(s, k)
        
        n = s.size
        return 0 if n < k || n == 0
        
        all_hash = {}
        
        (0..n-1).each do |i|
            unless all_hash[s[i]] 
                all_hash[s[i]] = 1
            else
                all_hash[s[i]] += 1
            end
        end
        
        if all_hash.values.min >= k
            return n
        end
        
        
        h = 0
        t = 0
        len  = 0
        while h < n 
            while h < n && all_hash[s[h]] < k
                h += 1
            end
            break if h == n
            t = h
            while t < n && all_hash[s[t]] >= k
                t += 1
            end
            # t == n or  all_hash[s[t]] < k
            local_len = longest_substring(s[h..t-1], k)
            len = len < local_len ? local_len : len
            h = t
        end
        len         
    end
    

Log in to reply
 

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