395. Longest Substring with At Least K Repeating Characters

Given a string s and an integer k, return the length of the longest substring of s such that the frequency of each character in this substring is greater than or equal to k.

My Answer 1: Output Limit Exceeded (30 / 31 test cases passed.)

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        if k > len(s):
            return 0
        
        i, j = 0, len(s)
        longest = 0
        isSubstr = 0
        
        while i < len(s):
            isSubstr = 0
            if i == j:
                i += 1
                j = len(s)
            string = s[i:j]
            count = collections.Counter(string)
            for val in count.values():
                if val < k:
                    isSubstr = 0
                    break
                else:
                    isSubstr = 1
            if isSubstr:
                longest = max(longest, len(string))
                if longest == len(s):   # a*3000개일 경우
                    return longest
            j -= 1
                    
        return longest

s[i:j] 로 substring 하나하나 만든 후 counter 계산해서 k 값이랑 비교하는 식으로 했는데

이런 테러블한 케이스에 막힘..;;

좀 비효율적이긴 해도 논리는 맞는 거 같은데...

Solution 1: Runtime: 32 ms - 90.84% / Memory Usage: 14.3 MB - 65.54%

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        
        if len(s)==0:
            return 0
        
        cnt = collections.Counter(s)
        
        for i in cnt:
            if cnt[i] < k:
                # print(s.split(i))
                return max(self.longestSubstring(p,k) for p in s.split(i))
                
        return len(s)

재귀로 longest Substring 구하기