[Leetcode 아주 상세한 문제풀이] 424. Longest Repeating Character Replacement - 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 42번 문제 Longest Repeating Character Replacement 다.

우선 문제를 살펴보자.

 

리트코드 42번 문제 Longest Repeating Character Replacement 링크

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

Longest Repeating Character Replacement - LeetCode

 

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.
 
Constraints:
1 <= s.length <= 105
s consists of only uppercase English letters.
0 <= k <= s.length

 

 

문제 설명

문제를 간략히 살펴보자. 인풋으로 문자열 s와 정수 k가 주어진다. 우리는 주어진 문자열에서 아무 문자나 하나 골라 문자열 내 존재하는 어떠한 문자로 바꿀 수 있다. 단, 이때 바꿀 수 있는 횟수는 k로 제한된다.

이때 문제에서 요구하는 바는 주어진 문자열에서 문자 하나를 골라 최대 k번 만큼 바꾸었을 때 같은 문자를 갖는 가장 긴 substring의 길이를 찾으라는 것이다. 문제 예시 2번을 살펴보면 문자열은 "AABABBA" 그리고 k값을 1로 주어졌다. 즉, 주어진 문자열에서 A 혹은 B를 하나 선택해 A는 B로 혹은 B는 A로 딱 1번 (=k) 바꿀 수 있다는 것이다. 그리고 그 문자열을 바꾸었을 때 연속되는 문자열로 이루어진 가장 긴 substring을 찾아 그 길이를 리턴하라는 것이다. 이 경우 우리는 B사이에 끼인 A를 B로 바꾸는 작업을 1회 하면 BBBB가 되어 가장 긴 substring의 길이는 4가 됨을 알 수 있다.

이제 문제를 풀어보자.

 

 

문제 접근법

사실 이 문제는 sliding window 문제와 굉장히 유사하다.

즉, 주어진 문자열에서 window 크기를 조절해가며 연속된 문자를 찾되 동시에 문자를 몇 번 바꿀 수 있는지 k값을 카운트 하는 것이다.

다음과 같은 순서로 문제에 접근할 수 있다.

1) 주어진 문자열에서 각 문자의 개수가 몇개인지 dictionary를 만들어 기록한다.

2) 문자열의 처음부터 오른쪽 방향으로 window 크기를 넓혀가며 문자 개수를 세어본다.

3) 만약 window 크기와 그 안에 있는 가장 흔한 문자 개수 차이가 k 보다 크다면 window를 왼쪽에서 한 칸 줄여준다. 우리는 같은 문자가 반복되는 substring을 찾고 있다. 즉, window 안에 있는 가장 흔한 문자를 제외한 문자를 가장 흔한 문자로 바꾸려고 한다. 따라서 그 차이가 k 보다 크다는 얘기는 window 안 모든 문자를 가장 흔한 문자로 모두 바꿀 수 없다는 얘기가 된다.

4) 이 과정을 반복하며 window 안에 있는 최대 길이의 substring을 기록해두고 모든 과정이 끝나면 최대 값이 리턴한다.

 

예시

이해를 돕기 위해  s = "AABACCA" and k = 2인 경우를 생각해 보자.

우리는 window 크기를 오른쪽으로 차례로 넓혀가며 그 크기가 5까지 다다랐다고 생각해보자.

이 경우 window 안에는 AABAC가 존재한다.

따라서 이 경우 k=2이기 때문에 B와 C를 A로 바꾸주면 AAAAA라는 길이가 5인 substring을 만들 수 있다.

이제 window 크기를 오른쪽으로 한 칸 더 넓혀주자.

이 경우 window안에는 AABACC가 존재한다.

가장 흔한 문자는 A이기 때문에 B와 C를 모두 A로 바꾸어주면 길이가 6인 substring을 만들 수 있다.

하지만 k=2이기 때문에 B 1개와 C 2개를 모두 A로 바꾸어 줄 수 없다.

따라서 이 경우 길이가 6인 A로만 이루어진 substring을 만들 수 없다.

즉, 이 경우 window 크기를 오른쪽으로 더 넓히더라도 어떻게 해도 A로만 이루어진 substring을 만들 수 없다.

따라서 다음 탐색을 위해서 window 크기를 왼쪽에서 한 칸 줄여준다.


이 과정을 주어진 문자열 전체에 대해 진행한다.

window 크기를 늘리고 줄이는 와중에 만들 수 있는 길이가 가장 긴 substring를 기록해둔다.

전체 탐색을 마치고 나면 그때 최대 길이를 갖는 substring의 길이를 리턴해주면 된다.

이제 코드로 한 번 살펴보자.

 

 

문제 풀이

문자열 s와 k 값을 입력받기 위한 함수를 정의해 준다. (line 1)

우선 문자열 내 각 문자의 개수를 카운트 하기 위해 dictionary를 하나 만들어 준다. (line 3)

최대 substring의 길이와 window내 가장 흔한 문자 개수를 카운트 하기 위해 변수를 만들어 준다. (line 4-5)

그리고 window의 시작점으로 이용하기 위한 left 포인터를 만들어 준다. (line 6)

우리는 주어진 문자열을 right 포인터를 이용하여 왼쪽에서 오른쪽으로 넓혀가며 탐색할 것이다. (line 8)

탐색을 진행하는 와중에 탐색하고 있는 문자의 개수를 카운트 해준다. (line 10)

그리고 window내 존재하는 가장 흔한 문자의 개수를 카운트 해준다. (line 12)

앞서 설명한대로 window 크기와 가장 흔한 문자 개수의 차이가 k값 보다 큰지 비교한다. (line 16)

만약 그 차이가 k 보다 크다면 k만큼 문자열을 바꾸어 주더라도 같은 문자의 substring을 만들 수 없다.

따라서 이 경우 left 포인터를 오른쪽으로 한 칸 옮겨주며 window에 left 포인터가 가리키는 문자 count를 하나 줄여주자. (line 17-18)

그리고 탐색 마지막에 가장 긴 substring의 길이를 업데이트 해준다.(line 21)

여기서 right-left+1로 표현한 이유는 이미 앞에서 if문을 통해 window 크기와 가장 흔한 문자 개수 차이가 k값 보다 큰지 비교했으므로, 이 경우 가장 흔한 문자 외 문자들은 k번의 변환을 통해 가장 흔한 문자로 바꿀 수 있다는 뜻이다.

따라서 window 크기 만큼이 가장 흔한 문자로만 이루어진 substring의 길이라고 할 수 있다.

모든 탐색을 마치고 나면 탐색 과정에서 찾은 가장 긴 substring의 길이를 리턴하고 종료한다. (line 23)

 

 

문제 풀이 코드

def characterReplacement(s, k):
    # Dictionary to keep track of the count of each letter
    count = {}
    max_length = 0
    max_count = 0  # The count of the most frequent character in the current window
    left = 0  # Left pointer for the sliding window
 
    for right in range(len(s)):
        # Update the count for the current character
        count[s[right]] = count.get(s[right], 0) + 1
        # Update the count of the most frequent character
        max_count = max(max_count, count[s[right]])
 
        # If the current window size minus the count of the most frequent character
        # is greater than k, shrink the window from the left
        if (right - left + 1) - max_count > k:
            count[s[left]] -= 1
            left += 1
 
        # Update the maximum length of the window seen so far
        max_length = max(max_length, right - left + 1)
 
    return max_length
 
# Example usage:
print(characterReplacement("ABAB", 2))  # Output: 4
print(characterReplacement("AABABBA", 1))  # Output: 4
 

 

 

관련 문제

리트코드 3번 Longest substring without repeating characters 문제풀이

리트코드 5번 Longest palindromic substring 문제풀이

리트코드 20번 Valid parenthesis 문제풀이

리트코드 49번 Group anagram 문제풀이

리트코드 76번 Minimum window substring 문제풀이

리트코드 125번 Valid palindrome 문제풀이

리트코드 242번 Valid anagram 문제풀이

리트코드 647번 Palindromic substrings문제풀이

 

 

424. Longest Repeating Character Replacement