[LeetCode] 424. Longest Repeating Character Replacement (c++, 슬라이딩 윈도우)

 

 

문제

 

https://leetcode.com/problems/longest-repeating-character-replacement/

Longest Repeating Character Replacement - LeetCode

 

 

풀이

 

난이도: Medium 

 

 

풀이를 이해하기도 힘들었던 어려운 문제였다.

 

 

일단 문자열의 최대길이는 50,000이므로 단순히 전부 시도해보는 것은 무리다.

 

 

정답인 위치의 subString을 생각해보자. 해당 subString은 하나의 대표 영문자로 대체되기 전에는 여러 문자들로 이루어져 있었다.

이때 subString은 x개의 대표 문자와 k개의 여러 문자들로 구성된다.

따라서 우리는 대표 문자의 개수인 x의 개수를 최대한 늘리는 subString를 찾으면 된다.

 

 

 

이때 슬라이딩 윈도우 기법을 이용하면 한 번의 search로 O(N)만에 답을 구할 수 있다.

슬라이딩 윈도우는 투 포인터와 비슷하다. (사실 투 포인터에 가까운 문제인 것 같지만 아무튼)

 

left와 right는 Window(Window)의 양쪽 끝을 가리키고,

아직 window의 크기가 x + k 보다 작다면 right를 오른쪽으로 이동시켜 window를 확장시키고,

x + k를 넘어섰다면 left를 오른쪽으로 이동시켜 window의 크기를 줄여 나간다.

 

코드에서 x(= maxFrequency)는 해당 window내의 가장 빈도수가 큰 문자의 개수를 의미한다.

이 maxFrequency는 윈도우의 크기가 변할 때마다 새로 값을 구해주어야 한다.

하지만, 새로 추가되거나 빠지는 값에서만 변동 여부를 확인하면 되므로 복잡하진 않다.

 

자세한 내용은 코드내 주석을 참조하자.

 

 

참조 풀이 

https://leetcode.com/problems/longest-repeating-character-replacement/discuss/208284/C%2B%2B-Sliding-Window-With-Detailed-Explanation-and-Thinking-Process

 

 

 

코드