[PS] Leet | 424. 가장 긴 반복되는 철자로 대체하기

문제

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.

예시

Example 1:
Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.

Example 2:
Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.
There may exists other ways to achieve this answer too.

조건

• 1 <= s.length <= 105
• s consists of only uppercase English letters.
• 0 <= k <= s.length

답

구간의 크기를 1에서 부터 하나씩 늘려가면서 같은 문자로 채울 수 있는 최대 구간의 크기를 확인합니다.

 

어떤 구간의 길이를 L, 가장 많이 등장하는 문자의 개수를 C라고 할 때,

 

특정 구간 내에서 L - C <= k 라면, 해당 구간은 모두 같은 문자로 바꿀 수 있습니다.

 

만약 L - C > k 가 된다면, 같은 크기의 구간을 한 칸 오른쪽으로 이동시키며 L - C = k 될 구간이 있는지 찾습니다.

 

만약 찾는다면, 거기서부터 다시 구간의 크기를 하나씩 늘려갑니다.

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var characterReplacement = function(s, k) {
    const cntMap = new Map();
    let maxCnt = 0;
    let maxRepCnt = 0;
    let start = 0;

    for (let i=0; i<s.length; ++i) {
        cntMap.set(s[i], (cntMap.get(s[i]) || 0) + 1);
        maxCnt = Math.max(maxCnt, cntMap.get(s[i]));

        if (i - start + 1 - maxCnt > k) {
            cntMap.set(s[start], cntMap.get(s[start]) - 1);
            start++;
        }

        maxRepCnt = Math.max(maxRepCnt, i - start + 1);
    }

    return maxRepCnt;
};

시간 복잡도 : O(n)

공간 복잡도 : O(1)