Python solution with detailed explanation

  • 0


    Longest Substring with At Least K Repeating Characters

    Brute force solution is O(N^2)

    • The longest substring can begin anywhere from [0, N-1]. We just do linear forward scan from each such position, recording the the frequencies and updating valid sets.
    from collections import defaultdict
    class Solution(object):
        def build_candidate(self, start, s, k):
            fmap, valid, last= defaultdict(int), set([]), -1
            for i in range(start, len(s)):
                fmap[s[i]] += 1
                if fmap[s[i]] >= k:
                if len(fmap) == len(valid):
                    last = i
            return 0 if last == -1 else last-start+1
        def longestSubstring(self, s, k):
            :type s: str
            :type k: int
            :rtype: int
            max_so_far = 0
            for i in range(len(s)):
                max_so_far = max(max_so_far, self.build_candidate(i, s, k))
            return max_so_far

    Divide and Conquer Approach

    • Find the character which has the least frequency. If the least frequency is more than k, then our answer is len(s). If the length of the string is less than k, return 0.
    • Otherwise split the string around this character and apply above to each string. Note this least frequency character can never be a part of a solution.
    • Note that instead of picking the rarest/least frequency character, we could have picked the first character with frequency less than k.
    • This is an N * lg N solution. Masters theorem: T(N) = b * T(N/b) + N. Now lg N will be the height of the recursion tree and it is limited by 26 or the alphabet size.
    • More details:
    class Solution(object):
        def helper(self, s, k):
            if len(s) < k:
                return 0
            ch = min(set(s), key=s.count)
            if s.count(ch) >= k:
                return len(s)
            return max(self.helper(t, k) for t in s.split(ch))
        def longestSubstring(self, s, k):
            :type s: str
            :type k: int
            :rtype: int
            return self.helper(s, k)

Log in to reply

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