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代码
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)