首页 > 试题广场 >

至多包含K种字符的子串

[编程题]至多包含K种字符的子串
  • 热度指数:1574 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个长度为 n 的字符串 s ,找出最多包含 k 种不同字符的最长连续子串的长度。

数据范围: , 字符串中仅包含小写英文字母
示例1

输入

"abcck",1

输出

2
示例2

输入

"abcck",2

输出

3

说明

最后三个字符 “cck” 组成最长子串 
package main
//import "fmt"

/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param s string字符串 
 * @param k int整型 
 * @return int整型
*/
func longestSubstring( s string ,  k int ) int {
    max:=0
    cnt:=map[byte]int{}
    for l,r:=0,0;r<len(s);r++{
        cnt[s[r]]++
        for len(cnt)>k{
            if cnt[s[l]]==1{
                delete(cnt,s[l])
            }else{
                cnt[s[l]]--
            }
            l++
        }
        if r-l+1>max{
            max=r-l+1
        }
    }
    return max
}

发表于 2023-03-16 15:12:59 回复(0)