带替换的最长重复子串

Question

在处理在线练习题时遇到了一个我似乎无法弄清楚的问题。我正在寻找一个字符串的最长长度，该字符串的字符只能被替换“k”次。因此，如果我们有“AABCCA”且 k = 2，那么输出将为 4，因为在“AAAACA”处，即将“..BC..”更改为“..AA..”，但如果 k = 1，则输出将为 3，因为更改后解将是“AACCA”或“AABCCC”。

我有以下代码，我相信它应该可以正常工作，但是我收到了运行时错误 - 所以我的部分肯定有一个明显的逻辑错误。这似乎与我如何改变 k 的值有关，它似乎想要将“-1”值与“0”值进行比较 - 但我不确定会发生什么。如有任何帮助，我们将不胜感激！

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        s_split = list(s)
        long_rep_sub = 0
        l = 0
        s_counter = 0 

        while l <= len(s_split)-1:
            r = l 
            while r <= len(s_split)-1 and k > 0:
                s_counter += 1
                if s_split[r] != s_split[l]:
                    k = k - 1
                r += 1    
            
            long_rep_sub = max(long_rep_sub,s_counter)
            l = r

        return (long_rep_sub)

Answer 1

您的滑动窗口方法尚未正确设置。我们还可以使用

Counter()

并利用

most_common()

:

from collections import Counter


class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        s_counter = Counter()
        l, long_rep_sub = 0, 0
        for r in range(len(s)):
            s_counter[s[r]] += 1
            max_count = s_counter.most_common(1)[0][1]
            if r - l + 1 - max_count > k:
                s_counter[s[l]] -= 1
                l += 1
            long_rep_sub = max(long_rep_sub, r - l + 1)
        return long_rep_sub


print(Solution().characterReplacement("AABCCA", k=2))
print(Solution().characterReplacement("AABCCA", k=1))

打印

4

3