2021-11-13:至少有 K 个重复字符的最长子串。给你一个字符串 s 和一个整数 k ,请你找出 s 中的最长子串, 要求
2023-03-14 22:57:27 时间
2021-11-13:至少有 K 个重复字符的最长子串。给你一个字符串 s 和一个整数 k ,请你找出 s 中的最长子串, 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。提示:1 <= s.length <= 10的4次方,s 仅由小写英文字母组成,1 <= k <= 10的5次方。力扣395。
答案2021-11-13:
滑动窗口,遍历26次。
时间复杂度:O(N)。
额外空间复杂度:O(1)。
代码用golang编写。代码如下:
package main
import "fmt"
func main() {
s := "ababbc"
k := 2
ret := longestSubstring1(s, k)
fmt.Println(ret)
ret = longestSubstring2(s, k)
fmt.Println(ret)
}
func longestSubstring1(s string, k int) int {
str := []byte(s)
N := len(str)
max := 0
for i := 0; i < N; i++ {
count := make([]int, 256)
collect := 0
satisfy := 0
for j := i; j < N; j++ {
if count[str[j]] == 0 {
collect++
}
if count[str[j]] == k-1 {
satisfy++
}
count[str[j]]++
if collect == satisfy {
max = getMax(max, j-i+1)
}
}
}
return max
}
func getMax(a, b int) int {
if a > b {
return a
} else {
return b
}
}
func longestSubstring2(s string, k int) int {
str := []byte(s)
N := len(str)
max := 0
for require := 1; require <= 26; require++ {
// 3种
// a~z 出现次数
count := make([]int, 26)
// 目前窗口内收集了几种字符了
collect := 0
// 目前窗口内出现次数>=k次的字符,满足了几种
satisfy := 0
// 窗口右边界
R := -1
for L := 0; L < N; L++ { // L要尝试每一个窗口的最左位置
// [L..R] R+1
for R+1 < N && !(collect == require && count[str[R+1]-'a'] == 0) {
R++
if count[str[R]-'a'] == 0 {
collect++
}
if count[str[R]-'a'] == k-1 {
satisfy++
}
count[str[R]-'a']++
}
// [L...R]
if satisfy == require {
max = getMax(max, R-L+1)
}
// L++
if count[str[L]-'a'] == 1 {
collect--
}
if count[str[L]-'a'] == k {
satisfy--
}
count[str[L]-'a']--
}
}
return max
}
执行结果如下:
[左神java代码](https://github.com/algorithmzuo/coding-for-great-offer/blob/main/src/class35/Problem_0395_LongestSubstringWithAtLeastKRepeatingCharacters.java)
相关文章
- 在 Go 里用 CGO?这 7 个问题你要关注!
- 9款优秀的去中心化通讯软件 Matrix 的客户端
- 求职数据分析,项目经验该怎么写
- 在OKR中,我看到了数据驱动业务的未来
- 火山引擎云原生大数据在金融行业的实践
- OpenHarmony富设备移植指南(二)—从postmarketOS获取移植资源
- 《数据成熟度指数》报告:64%的企业领袖认为大多数员工“不懂数据”
- OpenHarmony 小型系统兼容性测试指南
- 肯睿中国(Cloudera):2023年企业数字战略三大趋势预测
- 适用于 Linux 的十大命令行游戏
- GNOME 截图工具的新旧截图方式
- System76 即将推出的 COSMIC 桌面正在酝酿大变化
- 2GB 内存 8GB 存储即可流畅运行,Windows 11 极致精简版系统 Tiny11 发布
- 迎接 ecode:一个即将推出的具有全新图形用户界面框架的现代、轻量级代码编辑器
- loongarch架构介绍(三)—地址翻译
- Go 语言怎么解决编译器错误“err is shadowed during return”?
- 敏捷:可能被开发人员遗忘的部分
- Denodo预测2023年数据管理和分析的未来
- 利用数据推动可持续发展
- 在 Vue3 中实现 React 原生 Hooks(useState、useEffect),深入理解 React Hooks 的