質問する

kは、ある文字を他の文字

に変換することができる.
最長文字列長は(

個の同じ文字からなる)

に答える

デュアルポインタ

defaultdictストレージセグメント内の各アルファベット数

現在の長さ-最長文字<=kは

である必要があります.

from collections import defaultdict
class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        start, end = 0, 1
        memory = defaultdict(int)
        maxiLen = 0

        memory[s[start]] += 1
        while start <= end < len(s):
            thisLen = end - start
            if thisLen - max(memory.values()) <= k:
                # possible to extend
                maxiLen = max(maxiLen, thisLen)
                memory[s[end]] += 1
                end += 1
            else:
                # shrink the length
                memory[s[start]] -= 1
                start += 1
        if end - start - max(memory.values()) <= k:
            maxiLen = max(maxiLen, end-start)
        return maxiLen

結果

難しい問題ではありませんが、なぜ脳がこんなに鈍いのでしょうか.

スピードを上げる

from collections import defaultdict
class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        start, end = 0, 1
        memory = defaultdict(int)
        maxiLen = 0
        thisLen = 1
        lenS = len(s)

        memory[s[start]] += 1
        
        while end < lenS:
            if thisLen - max(memory.values()) <= k:
                # possible to extend
                maxiLen = max(maxiLen, thisLen)
                memory[s[end]] += 1
                end += 1
                thisLen += 1
            else:
                # shrink the length
                memory[s[start]] -= 1
                start += 1
                thisLen -= 1
        if thisLen - max(memory.values()) <= k:
            maxiLen = max(maxiLen, end-start)
        return maxiLen

一度に計算できるものはすべて一度に完成し、
現在のwindowの長さは毎回計算しないで、start、endをプラスして、言い逃れによって1増加あるいは減少します