Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.


Example 1:

Input:
s = "aaabb", k = 3

Output:
3

The longest substring is "aaa", as 'a' is repeated 3 times.



Example 2:

Input:
s = "ababbc", k = 2

Output:
5

The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

Difficulty: interview

Starter code:

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        

Solutions:
class Solution:
     def longestSubstring(self, s, k):
         """
         :type s: str
         :type k: int
         :rtype: int
         """
         for c in set(s):
             if s.count(c) < k:
                 return max(self.longestSubstring(sp, k) for sp in s.split(c))
         return len(s)

class Solution:
     def longestSubstring(self, s, k):
         """
         :type s: str
         :type k: int
         :rtype: int
         """
         
         # This works it just exceeds time limit
         characters = {}
         separators = set([])
 
         for char in s:
             char_count = characters.get(char, 0)
             characters[char] = char_count + 1
 
         for char, count in characters.items():
             if count < k:
                 separators.add(char)
 
         for i, char in enumerate(s):
             if char in separators:
                 return max(self.longestSubstring(s[0:i].rstrip(char), k), self.longestSubstring(s[i+1:].lstrip(char), k))
 
         return len(s)

class Solution:
     def longestSubstring(self, s, k):
         """
         :type s: str
         :type k: int
         :rtype: int
         """
         if not s:
             return 0
         for c in set(s):
             if s.count(c) < k:
                 return max(self.longestSubstring(t, k) for t in s.split(c))
         
         return len(s)

class Solution:
     def longestSubstring(self, s, k):
         """
         :type s: str
         :type k: int
         :rtype: int
         """
         for i in set(s):
             if s.count(i)<k:
                 return max(self.longestSubstring(t,k) for t in s.split(i))
         return len(s)

class Solution:
     def longestSubstring(self, s, k):
         """
         :type s: str
         :type k: int
         :rtype: int
         """
         if not s:
             return 0
         for c in set(s):
             if s.count(c) < k:
                 return max([self.longestSubstring(t, k) for t in s.split(c)])
         
         return len(s)

class Solution:
     def longestSubstring(self, s, k):
         """
         :type s: str
         :type k: int
         :rtype: int
         """
         
         if len(s) < k:
             return 0
         
         for c in set(s):
             if s.count(c) < k:
                 return max(self.longestSubstring(ss, k) for ss in s.split(c))
             
         return len(s)
             
         


class Solution:
     def longestSubstring(self, s, k):
         """
         :type s: str
         :type k: int
         :rtype: int
         """
         # str.count is much faster than collections.Counter under certain conditions
         # collections.Counter is intended to be a general tool
         # while str.count is much optimized C code to do just one thing 
         # (Counter in Py3 is written in C too)
         # see this SO question:
         # https://stackoverflow.com/questions/41594940/why-is-collections-counter-so-slow
         for c in set(s):
             if s.count(c) < k:
                 return max(self.longestSubstring(sub, k) for sub in s.split(c))
         return len(s)

class Solution:
     def longestSubstring(self, s, k):
         """
         :type s: str
         :type k: int
         :rtype: int
         """
         for c in set(s):
             if s.count(c) < k:
                 return max(self.longestSubstring(t, k) for t in s.split(c))
         return len(s)

class Solution:
     def longestSubstring(self, s, k):
         """
         :type s: str
         :type k: int
         :rtype: int
         """
         s_set = set(s)
         ans = -2147483647
         for c in s_set:
             if s.count(c) < k:
                 return max([self.longestSubstring(_s, k) for _s in s.split(c)])
         return len(s)