Blind 75 | Longest Repeating Character Replacement (Sliding Window 3 / 4)

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

Longest Repeating Character Replacement - LeetCode

 

 

Longest Repeating Character Replacement - 제일 긴 반복 문자 교체하기

 

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

 

문자열 s와 정수 k가 있다. 문자열의 어떤 문자든 선택해서 어떤 대문자로 k번 반복해서 바꿀 수 있다.

 

그 작업을 통해서 얻을 수 있는 1개의 같은 문자를 지닌 가장 긴 문자열을 리턴하라.

 

 

 

 

풀이

 

전 문제인 Longest Substring Without Repeating Characters와 비슷한 응용문제다.

 

맵으로 카운터를 만들어 한 문자씩 체크하며 문자열의 가장 큰 빈도수를 업데이트해준다.

 

만약 현재 문자의 길이 - 가장 큰 빈도수가 k보다 작다면 k로 원하는 문자로 전부 바꾸며 커버할 수 없다는 뜻이기에

 

left로 그 조건이 해당 안될 때까지 늘려준다.

 

right을 한 칸 더 늘려준 후 현재 문자열의 길이(right - left)를 longest length와 비교한 후 업데이트해 준다.

 

 

 

코드

 

 

가장 문제가 될 수 있는 지점은 17번 라인의 right - left + 1에서 off by 1 에러가 날 수 있는 점이다.

 

이런 계산 같은 경우에는 종이로 해결방법을 그려보며 떠올렸을 때는 괜찮지만 암산으로 하려면 쉽게 하는 실수다.