小黑leetcode之旅:95. 至少有 K 个重复字符的最长子串

小黑java解法1:分治法

class Solution {
    public int longestSubstring(String s, int k) {
        return dfs(s, 0, s.length() - 1, k);
    }
    public int dfs(String s, int left, int right, int k) {
        if (left > right) {
            return 0;
        }
        int[] cnt = new int[26];
        for (int i = left; i <= right; i++) {
            cnt[s.charAt(i) - 'a']++;
        }
        int res = 0;
        int start = left;
        boolean flag = false;
        System.out.println(left+"+"+right);
        for(int i = left; i <= right; i++) {
            if (cnt[s.charAt(i) - 'a'] < k) {
                System.out.println(i);
                int p = dfs(s, start, i-1, k);
                if(p > res){
                    res = p;
                }
                flag = true;
                start = i + 1;
            } 
        }
        if(flag){
            int p = dfs(s, start, right, k);
            if(p > res){
                res = p;
            }
            return res;
        }
        return right - left + 1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

小黑python解法1:分治法

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        l = len(s)
        
        def substring(s,start,end):
            counts = {}
            for c in s[start:end+1]:
                counts[c] = counts.get(c,0) + 1
            # 生成分割点
            splits = []
            for key in counts:
                if counts[key] < k:
                    splits.append(key)
            if not splits:
                return end - start + 1
            i = start
            res = 0
            while i <= end:
                while i <= end and s[i] in splits:
                    i += 1
                if i > end:
                    break
                start = i
                while i <= end and s[i] not in splits:
                    i += 1
                length = substring(s,start,i-1)
                res = max(length,res)
            return res
        return substring(s,0,l-1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

分治法

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        l = len(s)

        def subString(start,end):
            counts = {}
            # 记录子串中每一个字符的频率
            for c in s[start:end+1]:
                counts[c] = counts.get(c,0) + 1
            # 筛选出频率小于k的一个字符
            split = None
            for c in counts.keys():
                if counts[c] < k:
                    split = c
                    break
            # 所有字符符合要求,则return
            if not split:
                return end - start + 1
            i = start
            ans = 0
            while start <= end:
                while i <= end and s[i] == split:
                    i += 1
                if i > end:
                    break
                start = i
                while i <= end and s[i] != split:
                    i += 1
                ans = max(ans,subString(start,i-1))
            return ans
        return subString(0,l-1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31