from collections import Counter
import unittest

class Solution(object):
    ### time: O(N**3), space: O(N)
    def length_substring(self, string, k):
        """
        :type string: str
        :type k: int
        :rtype: int
        """ 
        if not string:
            return 0

        if k == 1:
            return len(string) # return the length of the entire string

        longest = 0

        for i in range(1, len(string)): # iterate over the string
            for j in range(0, i): # get all the possible susbstrings ending at i
                substring = string[j: i + 1] 
                if self.is_valid_substring(substring, k): # check if the current substring meets the criteria
                    longest = max(longest, len(substring))
        
        return longest
    
    def is_valid_substring(self, substring, k):
        """
        :type substring: str
        :type k: int
        :rtype : boolean
        """
        frequencies = Counter(substring)
        return all(frequencies[c] >= k for c in set(substring))
    
    # time: O(N**3), space: O(N)
    def length_substring2(self, string, k):
        """
        :type string: str
        :type k: int
        :rtype: int
        """
        if not string:
            return 0

        if k == 1:
            return len(string) # return the length of the entire string

        to_split = [string]
        longest = 0

        while to_split:
            t = to_split.pop()
            splitted = [t]
            freq = Counter(t)
            for c in freq:
                if freq[c] < k:
                    new_splitted = []
                    for spl in splitted:
                        new_splitted += spl.split(c)
                    splitted = new_splitted
            
            if len(splitted) == 1:
                longest = max(longest, len(splitted[0]))
            else:
                to_split += [sub for sub in splitted if len(sub) > longest]
        
        return longest

    def length_substring4(self, s, k):
        if not s or len(s) < k:
            return 0

        if k == 1:
            return len(s)
        
        longest = 0
        to_split = [s]

        while to_split:
            t = to_split.pop()
            frequencies = Counter(t)
            new_splitted = []

            for c in frequencies:
                if frequencies[c] < k: # t is splittable
                    new_splitted += t.split(c)
            
            if not new_splitted: # t is not splittable:
                longest = max(longest, len(t))
            else: # t was splittable, add the new splitted elements to to_split
                to_split += [sp for sp in new_splitted if len(sp) > longest]
        
        return longest

    # recursive method    
    def length_substring3(self, string, k):
        return self.helper(string, 0, len(string), k)

    def helper(self, string, start, end, k):
        if end - start < k:
            return 0
        
        substring = string[start : end]
        freq = Counter(substring)
        for i, c in enumerate(substring):
            if freq[c] < k: # found an infrequent char, split by it
                left = self.helper(string, start, i, k)
                right = self.helper(string, i + 1, end, k)
                return max(left, right)
        
        return end - start # all chars are frequent


class Test(unittest.TestCase):
    test_data = [('aaabb', 3, 3), ('ababbc', 2, 5), ('aabbccbcdeee', 3, 6)]
    def test_length_substring(self):
        solution = Solution()
        for data in self.test_data:
            actual = solution.length_substring4(data[0], data[1])
            self.assertEqual(actual, data[2])

if __name__ == '__main__':
    unittest.main()
