[슬라이딩 윈도우] Leet code 424. Longest Repeating Character Replacement

리트코드 424번
k번 변경을 통해 만들 수 있는 연속적으로 같은 가장 긴 문자열의 길이

시도 1🧨

• 먼저 처음에는 투포인터로 첫번째 문자 기준 가장 긴 윈도우 길이를 찾기
• 그 뒤에 max 윈도우 길이만큼 슬라이딩 윈도우
• 빈도수를 계산해서 만약 max를 넘을 수 있다면 오른쪽으로 포인터 옮겨가며 윈도우 최대 갱신

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:

        def maxInterval(alpa, head, tail, count):
            # 처음 연속되는 문자 뛰기
            while tail < len(s) and s[tail] == alpa:
                tail += 1

            # 다른 것들 최대한 바꾸기
            while tail < len(s) and count:
                if s[tail] != alpa:
                    count -= 1
                tail += 1

            # 마지막 연속되는 문자 뛰기
            while tail < len(s) and s[tail] == alpa:
                tail += 1

            # 첫 원소기준 가장 큰 window길이
            return tail - head

        max = maxInterval(s[0],0,0,k)

        head = 1

        while head + max -1 < len(s):
            freq = collections.Counter(s[head:head+max]).most_common(1)
            count = max-freq[0][1]
            if count <= k: # 최대길이가 같거나 길 가능성이 있을 때
                max = maxInterval(freq[0][0], head, head+max, k-count)

            head += 1


        return max

• 최대를 갱신할 때 오른쪽으로만 옮겨가면서 따져주는 것이 문제
• 가장 빈도수 높은 문자를 특정해서 윈도우 조절 -> 빈도수 높은 문자가 여러개 있을 때 알파벳순으로 높은 것만 따지게 된다

풀이1👍

• 빈도수 계산해서 만약 길어질 가능성 있다면 right 하나 증가
• 빈도수 계산시 길어질 가능성 없다면 left, right 둘다 증가
• right, left의 움직임에 따라 freq는 매번 갱신
• max값은 right - left이다 -> 최근 옮긴 right는 아직 같은지 다른지 판단 안됐기 때문!!

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        freqs = collections.defaultdict(int)
        left, right = 0, 0
        result = 0

        while right < len(s): # 끝에 다다르면 끝
            freqs[s[right]] += 1

            diff = right - left + 1 - max(freqs.values()) # 최대빈도와 다른 문자수
            if diff > k: # 가능성 아예 없는 경우
                freqs[s[left]] -= 1
                left += 1
                right += 1

            else: # 가능성 있는 경우
                right += 1
                result = right - left  # right 옮긴곳이 알파벳 모르기 때문에 하나 적게

        return result

• 최대길이를 구해야하기때문에 left는 작을수록 right는 클수록 좋다
• 먼저 right를 옮겨주고 가능성이 없어질때 left를 옮겨준다 -> 확실한 기준
• while문 돌 때마다 행동을 작게작게 정의한다

슬라이딩 윈도우는 기준점 찾기도 어렵고 아직 여러모로 어떻게 행동단위를 잘라야할지 언제 어떤 것을 해줘야할지 어렵다...🥲