README ¶
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
.
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)
代码
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
}
Documentation ¶
There is no documentation for this package.
Click to show internal directories.
Click to hide internal directories.