Lc395

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        """ tc O(26N) sc O(26)
        main idea: sliding window.  inorder to prevent right pointer keep moving to the end, set up a stop condition ---  when number of unique chars (max_unique)== uniques, stop moving right pointer and start moving left pointer instead.
        1.  set up a unique number 1-26. create a hash map counting occurance of each character; 
            a variable(number_of_unique) to track for current substring, number of unique character 
            a variable (number_of_least_k) to tract for current substring, number of unique character that has repeating chars >= k
        2.  keep moving right pointer while  number_of_unique <=  max_unique
        3.  start moving left pointer when number_of_unique > max_unique 
        4.  when number_of_unique == max_unique and number_of_least_k == max_unique, update result 
        """
        res  =  0
        for max_unique in range(1,27):
            char_cnt = collections.defaultdict(int)
            l = r =  number_of_unique = number_of_least_k =  0
            
            while r < len(s):
                cur = s[r]
                if number_of_unique <= max_unique:
                    char_cnt[cur] += 1 
                    if char_cnt[cur] == 1:
                        number_of_unique += 1
                    if char_cnt[cur] == k:
                        number_of_least_k += 1
                    r += 1 
                else: 
                    cur = s[l]
                    if char_cnt[cur] == 1:
                        number_of_unique -= 1
                    if char_cnt[cur] == k:
                        number_of_least_k -= 1  
                    char_cnt[cur] -= 1
                    l += 1
                if number_of_unique == max_unique and number_of_least_k == max_unique:
                    res = max(res,r-l) # (r +1) - l or  r - (l-1)
        return res 

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        """ tc O(N^2) sc O(N) for max recursion depth 
        main idea: divide and conquer
        XXXYXYXX  regard Y as char that has accumutice count < k,  Y here is a cut point to break s into substring 
        1. count any string s 
        2. edge case : not s -> return 0
        3. check if  cut_point exists
                                        if no: return whole string 
                                        if yes: go to step 4 (find the cutting point) 
    
        4. loop through current string until encounter cut point, use substring so far as target string for next recursion,  and compare with result to get max result 
        5. update current start point with next position of cut point.  repeat step4-5 until loop ends, return result 
        """
        res  =  0
        if not s: return res 
        cnt = Counter(s)
        no_cut = True 
        for key, val in cnt.items():
            if val < k: 
                no_cut = False
                break
        if no_cut: return len(s)
        start = end = 0
        while end < len(s):
            if cnt[s[end]] < k :
                res = max(res, self.longestSubstring(s[start:end],k))
                start = end +1 
            end += 1 
        res = max(res,self.longestSubstring(s[start:],k)) # when there is no cut point after substring[start:] 
        return res