395. Longest Substring with At Least K Repeating Characters - python3

1903 ワード
テキストリンク

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)
再帰的に最も長いSubstringを得る
[React] props
Java 8はConcurrentHashMapを開始し、なぜセグメントロックを捨てるのか