[LeetCode] 159. Longest Substring with At Most Two Distinct Characters

159. Longest Substring with At Most Two Distinct Characters

Medium

Given a string s, return the length of the longest substring that contains at most two distinct characters.

 

Example 1:

Input: s = "eceba"
Output: 3
Explanation: The substring is "ece" which its length is 3.

Example 2:

Input: s = "ccaabbb"
Output: 5
Explanation: The substring is "aabbb" which its length is 5.

 

Constraints:

• 1 <= s.length <= 10^5
• s consists of English letters.

---

문제 풀이

• 가장긴 부분 문자열을 찾아야한다. 
• 연결된 가장긴 문자열에는 알파벳이 두개만 존재해야한다.
• 딕셔너리(해쉬테이블, DAT) 를 사용해서 기록하고, 
• 이를 이용하여 슬라이딩 윈도우(투포인터)로 문제를 푼다.
• 두번째 포인터를 계속 옮기면서 딕셔너리에 갯수를 세어준다.
• 만약 딕셔너리에 있는 알파벳 갯수가 2를 넘으면, 해당 위치의 딕셔너리 갯수를 줄여준다.
• 알파벳의 개수가 0이면 딕셔너리에서 제거해줘야 전체 갯수를 셀때 편리하다.
• 추가적으로, 답을 구할때 알파벳의 갯수가 2를 넘지 않을때만 최대값을 계산해줘야한다. 

소스 코드

class Solution:
    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
        cnt = defaultdict(int)
        p1, p2, res = 0, 0, 0
        while p2 < len(s):
            cnt[s[p2]] += 1
            if len(cnt) > 2:
                cnt[s[p1]] -= 1
                if cnt[s[p1]] == 0:
                    del(cnt[s[p1]]) 
                p1 += 1
            else:
                res = max(res, sum(cnt.values()))
            p2 += 1
        return res