[Leetcode] 0424. 가장 긴 반복 문자 대체

Python, C++, JavaScript, SQL 및 TypeScript의 다양한 LeetCode 솔루션을 살펴보세요. 여러 프로그래밍 언어로 인터뷰 준비, 학습 및 코드 연습에 적합합니다. Github 레포 링크

중간

문자열이 주어집니다 에스 그리고 정수 케이. 문자열의 모든 문자를 선택하여 다른 대문자 영어 문자로 변경할 수 있습니다. 이 작업은 최대 케이 타임스.

반품 위의 작업을 수행한 후 얻을 수 있는 동일한 문자를 포함하는 가장 긴 하위 문자열의 길이.

예시 1:

입력: s = "ABAB", k = 2
산출: 4
설명: 두 개의 'A'를 두 개의 'B'로 바꾸거나 그 반대로 하세요.

예 2:

입력: s = "아바바바", k = 1
산출: 4
설명: 가운데에 있는 'A'를 'B'로 바꿔서 "AABBBBA"를 만들어 보세요. 하위 문자열 "BBBB"는 가장 긴 반복 문자가 있는데, 4개입니다. 이 답을 얻는 다른 방법도 있을 수 있습니다.

제약:

1 <= s.length <= 10 ⁵
에스 대문자 영어 글자로만 구성됩니다.
0 <= k <= s.길이

파이썬

				
					# 시간 복잡도: O(n) # 공간 복잡도: O(1) from collections import defaultdict class 솔루션: def characterReplacement(self, s: str, k: int) -> int: result = 0 left = right = 0 freq = defaultdict(int) mostFreqChar = 0 오른쪽 범위(길이(s))에 대해 freq[s[오른쪽]] += 1 mostFreqChar = max(mostFreqChar, freq[s[오른쪽]]) 오른쪽 - 왼쪽 + 1 - mostFreqChar > k: freq[s[left]] -= 1 left += 1 result = max(result, right - left + 1) return result s = "AABABBA" k = 1 print(Solution().characterReplacement(s, k ))

중간

파이썬

관련 기사