Leetcode 1156:单字符重复子串的最大长度(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1156:单字符重复子串的最大长度(超详细的解法!!!)

in leetcode with 0 comment

如果字符串中的所有字符都相同,那么这个字符串是单字符重复的字符串。

给你一个字符串 text,你只能交换其中两个字符一次或者什么都不做,然后得到一些单字符重复的子串。返回其中最长的子串的长度。

示例 1:

输入:text = "ababa"
输出:3

示例 2:

输入:text = "aaabaaa"
输出:6

示例 3:

输入:text = "aaabbaaa"
输出:4

示例 4:

输入:text = "aaaaa"
输出:5

示例 5:

输入:text = "abcdef"
输出:1

提示:

解题思路

这个问题和之前的问题Leetcode 424:替换后的最长重复字符(超详细的解法!!!)非常类似,相当于之前问题中的k=1的情况,但是我们需要考虑一个边界问题,例如第二个例子aaabaaa,此时按照之前的算法,我们得到的最大长度就是7,但是实际上我们并没有额外的ab进行交换了,这就是我们需要考虑的问题。实际上这个边界情况很好去除,只要最后取min(最大窗口长度,最大窗口中出现最多的字符数在整个字符串中的个数)即可。很绕口啊,举个例子,例如aaabaaa,此时的最大窗口就是这样

a a a b a a a
↑           ↑
l           r

此时最大窗口中出现最多的元素就是a,而a在整个字符串中的出现次数是6,所以我们最后的结果就应该是min(窗口大小7,a的个数6)=6

class Solution:
    def maxRepOpt1(self, s: str) -> int:
        res, n, l, mf, mc = 0, len(s), 0, 0, s[0]
        d = collections.defaultdict(int)
        for r, c in enumerate(s):
            d[c] += 1
            if d[c] > mf:
                mf, mc = d[c], c
                
            while r - l + 1 - mf > 1:
                d[s[l]] -= 1
                l += 1
            res = max(res, r - l + 1)
        return min(res, collections.Counter(s)[mc])

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses