Leetcode Python - 424. Longest Repeating Character Replacement

Leetcode #424 - Longest Repeating Character Replacement

이제 blind 75 leetcode를 풀어보겠습니다. https://leetcode.com/discuss/interview-question/460599/Blind-75-LeetCode-Questions

리트코드의 문제 424 ‘Longest Repeating Character Replacement’을 파이썬으로 풀어 보도록 하겠습니다.

discuss 참고, 포인트는 dictionary에 char를 넣으면서, 시작점과 현재 지점 사이의 최대값을 뺀게 k 이하이면 start를 하나 앞으로 넣어줍니다.

예를 들어, AABABBA, k=1이 있으면 처음 AABA까지는 최대가 될 수 있습니다. (B를 A로 한번 바꿀 수 있으므로) 다음 AABAB케이스에서는 k=1인 상태로 B가 2개이므로 모두 바꿀 수 없습니다. 그래서 처음 A를 시작점에서 앞으로 이동합니다.

전체 코드는 아래와 같습니다.

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        maxCount, start = 0, 0
        ret = 0
        seen = {}
        
        for i,c in enumerate(s):
            seen[c] = seen.get(c,0) + 1
            maxCount = max(maxCount, seen[c])
            
            if i - start + 1 - maxCount > k:
                seen[s[start]] -= 1
                start += 1
            
            ret = max(ret, i-start+1)
        return ret

for loop안에 while이 아닌 if 를 쓴 이유는, maximum값을 구하는 것이기 때문에 slice window를 줄일 필요가 없어서 입니다.

시간복잡도는

• O(n) : 한번의 loop

공간복잡도는

• O(n) : 최악의 경우(ABCD… 모두 다른 경우, seen에 모두 들어감)