[알고리즘] Leetcode #424 가장 긴 반복 문자 대체 (Python)

---

↓↓↓ 아래는 내 리트코드 계정 ↓↓↓

leetcode.com/Jiwon_Lee/

Jiwon Lee - LeetCode Profile

 

---

문제 설명

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.

 

Constraints

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

 

Code

def characterReplacement(self, s, k):
    left = right = 0
    counts = collections.Counter()
    
    for right in range(1, len(s) + 1):
        counts[s[right - 1]] += 1
        #가장 흔하기 등장하는 문자 탐색
        max_char_n = counts.most_common(1)[0][1]
        
        # k초과 시 왼쪽 포인터 이동
        if right - left - max_char_n > k:
            counts[s[left]] -= 1
            left += 1
    
    return right - left # 최댓값 구하는 부분 생략

이 문제는 투포인터와 슬라이딩 윈도우, Counter를 모두 사용한다. 주어진 k값 이내의 변경으로 연속으로 반복된 문자열을 만들어야 하므로 right pointer와 left pointer 사이 길이에서 최대 출현 문자의 길이 (max_char_n)만큼을 빼준 값이 k보다 크도록 하면 된다. 마지막으로, 변경해야 할 문자의 길이가 제한 k를 초과하는 경우 왼쪽 pointer를 오른쪽으로 한 칸씩 이동시키면서 조정한다. 이때, counts 내 구성요소에서도 left에 포함되었던 문자를 제거해준다. 여기에서는 슬라이딩 윈도우 크기의 최댓값을 구하는 코드를 제거했는데, 한번 right - left가 최대값이 되면 이후엔 right pointer의 오른쪽 이동과 더불어 left pointer도 오른쪽으로 이동하기 때문에 최댓값을 갱신할 필요가 없어지기 때문이다.

 

---

 

 

I'm a Senior Student in Data Science ! 

데이터 사이언스를 공부하고 있는 학부생의 TIL 블로그입니다. 게시글이 도움 되셨다면 구독과 좋아요 :)