前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >golang刷leetcode 滑动窗口(6)替换后的最长重复字符

golang刷leetcode 滑动窗口(6)替换后的最长重复字符

作者头像
golangLeetcode
发布2022-08-02 15:54:33
3710
发布2022-08-02 15:54:33
举报
文章被收录于专栏:golang算法架构leetcode技术php

给你一个仅由大写英文字母组成的字符串,你可以将任意位置上的字符替换成另外的字符,总共可最多替换 k 次。在执行上述操作后,找到包含重复字母的最长子串的长度。

注意: 字符串长度 和 k 不会超过 104。

示例 1:

代码语言:javascript
复制
输入:
s = "ABAB", k = 2

输出:
4

解释:
用两个'A'替换为两个'B',反之亦然。

示例 2:

代码语言:javascript
复制
输入:
s = "AABABBA", k = 1

输出:
4

解释:
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。

解题思路

1,滑动窗口类题目一般都需要左右两个指针,重点放在理解和优化窗口移动的逻辑

2,注意本题是提换K个字符而不是替换K种

3,显然最大长度=窗口内出现次数最多的字符的次数+K

4,每次移动右指针,更新最大出现次数

5,如果右指针到左指针长度>K+最大出现次数则,移动左指针

代码语言:javascript
复制
func characterReplacement(s string, k int) int {
    win:=make(map[byte]int)
    start:=0
    max:=0
    maxSame:=0

    for end:=0;end<len(s);end++{
        win[s[end]]++
        if win[s[end]]>maxSame{
            maxSame=win[s[end]]
        }
        for end-start+1-maxSame>k{
             win[s[start]]--
            start++
        }
         fmt.Println("*",start,end,maxSame)
        if end-start+1>max{
            max=end-start+1
        }
    }
    return max
}
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-03-21,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 golang算法架构leetcode技术php 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档