← 전체 회차
A-017● Day 172026.05.19mediumleetcode #424neetcode150

가장 긴 반복 문자 치환

#hash-table#string#sliding-window
↗ leetcode #424 · longest-repeating-character-replacement
01

문제

· problem
P.017

가장 긴 반복 문자 치환

↗ leetcode #424

문자열 s와 정수 k가 주어집니다. 문자열의 임의의 문자를 다른 대문자로 변경할 수 있으며, 이 작업을 최대 k번 수행할 수 있습니다. 주어진 작업을 수행하여 얻을 수 있는 같은 문자로만 이루어진 가장 긴 부분 문자열의 길이를 반환하세요.

제약
  • · 1 ≤ s.length ≤ 10^5
  • · s consists of only uppercase English letters
  • · 0 ≤ k ≤ s.length
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
"ABAB"
2
4
example 2input → output
"AABABBA"
1
4
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    k=0일 때 (변경할 수 없음) 결과는 무엇인가요?
  • ☐
    부분 문자열이 반드시 연속되어야 하나요?
  • ☐
    같은 문자로만 이루어진 부분 문자열을 만들 때, 어느 문자로 변경해야 가장 효율적인가요?
  • ☐
    변경 가능한 최대 횟수 k를 정확히 모두 사용해야 하나요?
  • ☐
    윈도우 크기가 고정되어 있나요?
  • ☐
    실제로 문자열을 수정해야 하나요?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 문자 빈도 맵 초기화
○
count = {}
○
count = []
○
count = set()
step 2· 좌측 포인터 초기화
○
l = 0
○
l = -1
○
l = r
step 3· 최대 빈도 추적 초기화
○
maxf = 0
○
maxf = 1
step 4· 우측 포인터로 윈도우 확장│ 중첩
○
for r in range(len(s)):
○
for r in range(1, len(s)):
step 5· 새 문자의 빈도 증가│ │ 중첩
○
count[s[r]] = 1 + count.get(s[r], 0)
○
count[s[r]] += 1
○
count[s[r]] = count[s[r]] + 1
step 6· 최대 빈도 업데이트│ │ 중첩
○
maxf = max(maxf, count[s[r]])
○
maxf = max(maxf, max(count.values()))
step 7· 윈도우 유효성 검증│ │ 중첩
○
if (r - l + 1) - maxf > k:
○
if (r - l + 1) - maxf >= k:
○
if (r - l) - maxf > k:
step 8· 좌측 문자 카운트 감소 및 포인터 이동│ │ │ 중첩
○
count[s[l]] -= 1
○
del count[s[l]]
○
count[s[l]] = 0
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

· solve
solution.py
1
class Solution:
2
    def characterReplacement(self, s: str, k: int) -> int:
3
        count = {}
4
5
        l = 0
6
        maxf = 0
7
        for r in range(len(s)):
8
            count[s[r]] = 1 + count.get(s[r], 0)
9
            maxf = max(maxf, count[s[r]])
10
11
            if (r - l + 1) - maxf > k:
12
                count[s[l]] -= 1
13
                l += 1
14
15
        return (r - l + 1)
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
"ABAB"
2
→
4
case 2
"AABABBA"
1
→
4
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.