📕문제

[LeetCode] 424. Longest Repeating Character Replacement

문제 설명

대문자로 이루어져있는 문자열과 k가 주어졌을 때, k개만큼 문자를 교체해서 만들 수 있는 같은 문자로 이루어진 부분 문자열의 최대 길이를 구하는 문제다.

---

📝풀이

알고리즘 스터디에서 푼 문제 중 처음으로 내 힘으로 해결하지 못한 문제다..
투포인터를 사용해야될 것 같긴 한데 내가 생각한 방법으론 도저히 시간복잡도를 $O(N^2)$보다 낮게 줄일 수 없었다.
결국 해당 문제의 solutions에 올라온 코드 중 하나를 참고해 해결하였다.

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        if len(s) == k:
            return k
        s_set = set(s)
        result = set()
        for char in s_set:
            left, right, count = 0, 0, 0
            while right < len(s):
                if s[right] == char:
                    right += 1
                elif count < k:
                    count += 1
                    right += 1
                elif s[left] == char:
                    left += 1
                else:
                    count -= 1
                    left += 1
                result.add(right-left)
        return max(result)

• 바꿀 수 있는 문자의 개수가 k개인 경우, 만들 수 있는 부분 문자열의 최대 길이는 이와 같으므로 바로 반환한다.
• s에 있는 문자의 종류만큼 탐색을 하게된다. = char
• 검사할 윈도우의 시작 인덱스인 left, 끝 인덱스인 right, 해당 윈도우에서 바꾼 문자의 수인 count를 조작하며 탐색이 진행된다.
• right를 먼저 조작하게 된다.
  • 윈도우의 끝값이 char와 같다면 윈도우의 크기를 한 칸 늘린다.
  • 윈도우의 끝값이 char와 다르고 바꾼 문자의 개수가 k보다 작으면, count를 증가시키고 윈도우의 크기를 한 칸 늘린다.
• 위 두가지 경우가 아니라면 left를 조작한다.
  • 윈도우의 시작값이 char와 같다면 윈도우의 크기를 한 칸 줄인다.
  • 윈도우의 시작값이 char와 다르다면 count를 감소시키고 윈도우의 크기를 한 칸 줄인다.
• 탐색을 진행하며 result에 윈도우의 크기를 저장한다.
• 가능한 윈도우의 크기 중 최대값을 반환한다.