Longest Substring with At Least K Repeating Characters https://leetcode.com/problems/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: valid.add(s[i]) 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: https://discuss.leetcode.com/topic/57092/4-lines-python/7
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)