mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-08 10:24:58 +08:00
112 lines
3.7 KiB
Markdown
112 lines
3.7 KiB
Markdown
# [395. Longest Substring with At Least K Repeating Characters](https://leetcode.com/problems/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`.
|
||
|
||
**Example 1:**
|
||
|
||
```
|
||
Input: s = "aaabb", k = 3
|
||
Output: 3
|
||
Explanation: The longest substring is "aaa", as 'a' is repeated 3 times.
|
||
```
|
||
|
||
**Example 2:**
|
||
|
||
```
|
||
Input: s = "ababbc", k = 2
|
||
Output: 5
|
||
Explanation: The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.
|
||
```
|
||
|
||
**Constraints:**
|
||
|
||
- `1 <= s.length <= 10^4`
|
||
- `s` consists of only lowercase English letters.
|
||
- `1 <= k <= 10^5`
|
||
|
||
## 题目大意
|
||
|
||
给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。
|
||
|
||
## 解题思路
|
||
|
||
- 最容易想到的思路是递归。如果某个字符出现次数大于 0 小于 k，那么包含这个字符的子串都不满足要求。所以按照这个字符来切分整个字符串，满足题意的最长子串一定不包含切分的字符。切分完取出最长子串即可。时间复杂度 O(26*n)，空间复杂度 O(26^2)
|
||
- 此题另外一个思路是滑动窗口。有一个需要解决的问题是右窗口移动的条件。此题要求最长字符串，那么这个最终的字符串内包含的字符种类最多是 26 种。字符种类就是右窗口移动的条件。依次枚举字符种类，如果当前窗口内的字符种类小于当前枚举的字符种类，那么窗口右移，否则左移。窗口移动中需要动态维护 freq 频次数组。可以每次都循环一遍这个数组，计算出出现次数大于 k 的字符。虽然这种做法只最多循环 26 次，但是还是不高效。更高效的做法是维护 1 个值，一个用来记录当前出现次数小于 k 次的字符种类数 `less`。如果 freq 为 0 ，说明小于 k 次的字符种类数要发生变化，如果是右窗口移动，那么 `less++`，如果是左窗口移动，那么`less--`。同理，如果 freq 为 k ，说明小于 k 次的字符种类数要发生变化，如果是右窗口移动，那么 `less--`，如果是左窗口移动，那么`less++`。在枚举 26 个字符种类中，动态维护记录出最长字符串。枚举完成，最长字符串长度也就求出来了。时间复杂度 O(26*n)，空间复杂度 O(26)
|
||
|
||
## 代码
|
||
|
||
```go
|
||
package leetcode
|
||
|
||
import "strings"
|
||
|
||
// 解法一 滑动窗口
|
||
func longestSubstring(s string, k int) int {
|
||
res := 0
|
||
for t := 1; t <= 26; t++ {
|
||
freq, total, lessK, left, right := [26]int{}, 0, 0, 0, -1
|
||
for left < len(s) {
|
||
if right+1 < len(s) && total <= t {
|
||
if freq[s[right+1]-'a'] == 0 {
|
||
total++
|
||
lessK++
|
||
}
|
||
freq[s[right+1]-'a']++
|
||
if freq[s[right+1]-'a'] == k {
|
||
lessK--
|
||
}
|
||
right++
|
||
} else {
|
||
if freq[s[left]-'a'] == k {
|
||
lessK++
|
||
}
|
||
freq[s[left]-'a']--
|
||
if freq[s[left]-'a'] == 0 {
|
||
total--
|
||
lessK--
|
||
}
|
||
left++
|
||
}
|
||
if lessK == 0 {
|
||
res = max(res, right-left+1)
|
||
}
|
||
|
||
}
|
||
}
|
||
return res
|
||
}
|
||
|
||
func max(a, b int) int {
|
||
if a > b {
|
||
return a
|
||
}
|
||
return b
|
||
}
|
||
|
||
// 解法二 递归分治
|
||
func longestSubstring1(s string, k int) int {
|
||
if s == "" {
|
||
return 0
|
||
}
|
||
freq, split, res := [26]int{}, byte(0), 0
|
||
for _, ch := range s {
|
||
freq[ch-'a']++
|
||
}
|
||
for i, c := range freq[:] {
|
||
if 0 < c && c < k {
|
||
split = 'a' + byte(i)
|
||
break
|
||
}
|
||
}
|
||
if split == 0 {
|
||
return len(s)
|
||
}
|
||
for _, subStr := range strings.Split(s, string(split)) {
|
||
res = max(res, longestSubstring1(subStr, k))
|
||
}
|
||
return res
|
||
}
|
||
``` |