395. Longest Substring with At Least K Repeating Characters

https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/

solution

• 滑动窗口

from collections import defaultdict

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        if not s: return 0
        n = len(s)
        max_num = len(set(s))

        # 当不同字符个数为num，最长字符为多少
        def cal(num):
            left = 0
            # 目前不同字符的个数
            cur = 0
            # 大于等于k字符的个数
            ge_k = 0
            # 记录字符个数
            c = defaultdict(int)
            # 最长字符串
            res = 0
            for right in range(n):
                c[s[right]] += 1
                # 不同字符个数
                if c[s[right]] == 1:
                    cur += 1
                # 大于等于k个数
                if c[s[right]] == k:
                    ge_k += 1
                # 当字符串不同个数大于 num
                while cur > num:
                    if c[s[left]] == 1:
                        cur -= 1
                    if c[s[left]] == k:
                        ge_k -= 1
                    c[s[left]] -= 1
                    left += 1
                if ge_k == num:
                    res = max(res, right - left + 1)
            return res

        return max(cal(num) for num in range(1, max_num + 1))

时间复杂度：O() 空间复杂度：O()

• 分治

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        if len(s) == 0 or k > len(s):
            return 0
        c = Counter(s)

        for i, letter in enumerate(s):
            if c[letter] < k:
                sub1 = self.longestSubstring(s[:i], k)
                sub2 = self.longestSubstring(s[i+1:], k)
                break
        else:
            return len(s)
        return max(sub1, sub2)

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        if len(s) < k:
            return 0
        # 找个字符串个数最少的字符
        t = min(set(s), key=s.count)
        # 最少字符的个数都大于等于k
        if s.count(t) >= k:
            return len(s)
        return max(self.longestSubstring(a, k) for a in s.split(t))

• 前缀和

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        from collections import Counter
        c = Counter()
        n = len(s)
        prefix = [c.copy()]
        for i in range(n):
            c[s[i]] += 1
            prefix.append(c.copy())

        def check(tmp):
            for val in tmp.values():
                if val < k:
                    return False
            return True

        res = 0
        for i in range(n + 1):
            for j in range(i):
                if check(prefix[i] - prefix[j]):
                    res = max(res, i - j)
                    break
        return res