문제

• 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씩 늘리거나 줄여줬다