Python Soltuion in easy to understand blocks


  • 0
    P
    class Solution(object):
        def longestSubstring(self, s, k):
            """
            :type s: str
            :type k: int
            :rtype: int
            """
            # corner case
            if len(s) < k or k == 0:
                return 0
            # get counts
            count = collections.defaultdict(int)
            for c in s:
                count[c] += 1
            # get qualified ranges by ignoring chars with freq < k
            ranges = []
            begin = end = 0
            while end < len(s):
                if count[s[end]] < k:
                    if end - begin >= k:
                        ranges.append((begin, end))
                    begin = end + 1
                end += 1
            # add the last range
            if end - begin >= k:
                ranges.append((begin, end))
            # base case
            # The whole range will be added to the list
            # when all the chars in the string have freq >= k
            if len(ranges) == 1 and end-begin == len(s):
                return end - begin
            # computation if not base case,
            maxLen = 0
            for i, j in ranges:
                maxLen = max(maxLen, self.longestSubstring(s[i:j], k))
            return maxLen
            
    

Log in to reply
 

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