本文主要是介绍【LeetCode430】至多包含 K 个不同字符的最长子串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
340. 至多包含 K 个不同字符的最长子串
难度困难91收藏分享切换为英文接收动态反馈
给定一个字符串 s ，找出 至多 包含 k 个不同字符的最长子串 T。
示例 1:
输入: s = "eceba", k = 2 输出: 3 解释: 则 T 为 "ece"，所以长度为 3。
示例 2:
输入: s = "aa", k = 1 输出: 2 解释: 则 T 为 "aa"，所以长度为 2。
思路：【滑动窗口+ hash】
创建一个map，不停把右边元素放进map，控制里面只有k个元素；每次移除最左边那个元素，map中存index， 每次遇到相同的key时直接把前面那个index覆盖，这样index中最小的就是最左边那个
Talk is cheap， show me the code
package mainimport "math"func main() {lengthOfLongestSubstringKDistinct("eceba", 2)
}func lengthOfLongestSubstringKDistinct(s string, k int) int {if s == "" || k == 0{return 0}m := make(map[string]int, 2)var res = 1left, right := 0, 0for right < len(s) {// value 为对应值对应的index索引m[string(s[right])]=rightright++// 如果窗口内的字符数超过了k，要滑动左边界让其回到k以内// 移去最左出现的字符，移动left指针使得滑动窗口只包含k个不同字符// 本题的核心处理：维护map中只有k个元素；每次移除最左边那个，// map中存index，每次遇到相同的key时直接把前面那个index覆盖，这样index中最小的就是最左边的if len(getKeys(m)) > k {// 选出value中最左边的进行删除minIndex := math.MaxInt64for _, value := range m {if value < minIndex {minIndex = value}}delete(m, string(s[minIndex]))// 左边跳转到加1left = minIndex + 1}if right - left > res {res = right-left}}for key, value := range m {if value == 0 {delete(m, key)}}print(res)return res
}func getKeys(m map[string]int) []string {// 数组默认长度为map长度,后面append时,不需要重新申请内存和拷贝,效率较高keys := make([]string, 0, len(m))for k, _ := range m {keys = append(keys, k)}return keys
}
这篇关于【LeetCode430】至多包含 K 个不同字符的最长子串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
