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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
| // @Title: 至少有 K 个重复字符的最长子串 (Longest Substring with At Least K Repeating Characters)
// @Author: 15816537946@163.com
// @Date: 2019-09-01 20:39:38
// @Runtime: 64 ms
// @Memory: 8.1 MB
/*
* @lc app=leetcode.cn id=395 lang=golang
*
* [395] 至少有K个重复字符的最长子串
*
* https://leetcode-cn.com/problems/longest-substring-with-at-least-k-repeating-characters/description/
*
* algorithms
* Medium (40.58%)
* Likes: 61
* Dislikes: 0
* Total Accepted: 3.5K
* Total Submissions: 8.7K
* Testcase Example: '"aaabb"\n3'
*
* 找到给定字符串(由小写字符组成)中的最长子串 T , 要求 T 中的每一字符出现次数都不少于 k 。输出 T 的长度。
*
* 示例 1:
*
*
* 输入:
* s = "aaabb", k = 3
*
* 输出:
* 3
*
* 最长子串为 "aaa" ,其中 'a' 重复了 3 次。
*
*
* 示例 2:
*
*
* 输入:
* s = "ababbc", k = 2
*
* 输出:
* 5
*
* 最长子串为 "ababb" ,其中 'a' 重复了 2 次, 'b' 重复了 3 次。
*
*
*/
// dfs
func longestSubstring(s string, k int) int {
n := len(s)
sig := make([]int,26)
for i := range s {
sig[int(s[i]-'a')]++
}
for i := range s {
if sig[int(s[i]-'a')] < k {
a := longestSubstring(s[:i],k)
b := longestSubstring(s[i+1:],k)
if a > b {
b = a
}
return b
}
}
return n
}
|