[ leetcode ] Longest Substring with At Most Two Distinct Characters

https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/

요즘 알고리즘은 통 안풀다가 오랜만에 리트코드를 켰다.

그리고 만난 문제

Longest Substring with At Most Two Distinct Characters

문제 설명은 다음과 같다.

오직 두 종류의 문자로 이루어진 가장 긴 연속된 부분 문자열의 길이를 구하시오.

문제를 보니 백준 회전 초밥 문제가 생각 나서 caterpillar method라는 방법으로 풀었다.

https://codility.com/media/train/13-CaterpillarMethod.pdf

위 링크는 해당 방법에 대한 pdf. 공부해 놓으면 다양하게 응용 가능하다.

import collections


class Solution:

    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
        start = 0
        end = 0

        letterCounter = collections.defaultdict(int)
        letterKey = set()
        answer = 0
        cur_string = collections.deque([])

        def addLetter(value):
            letterCounter[value] += 1
            letterKey.add(value)

        def deleteLetter(value):
            if letterCounter[value] == 1:
                letterKey.remove(value)
            letterCounter[value] -= 1

        def isAddable(value):
            return any([
                value in letterKey and len(letterKey) <= 2,
                value not in letterKey and len(letterKey) < 2
            ])

        while (start < len(s) and end < len(s)):
            if isAddable(s[end]):
                addLetter(s[end])
                cur_string.append(s[end])
                answer = max(answer, len(cur_string))
                end += 1
            else:
                deleteLetter(s[start])
                cur_string.popleft()
                start += 1
        return answer