[Python] leetcode-3090.Maximum Length Substring With Two Occurrences

처음 문제를 보고 엇? 쉽네 했다가 어떻게 풀지 방법을 생각하니까 다시 뇌정지가 오고,,반복하다가 슬라이딩 윈도우를 통해 풀면 되겠다는 생각이 들었다!!

한 개의 문자가 몇 번 나오는지 세면서 그 횟수가 (문제에 주어진대로) 두 번을 초과하면 문자열의 가장 앞에 있는 것부터 제거해나가면서 최대 갯수를 유지하도록 하는 방법을 떠올렸다.

이걸 구현하려면,,,,흠....!

일단,

---

1. 문자의 빈도를 세기 위해 collections의 defaultdict를 사용했다.😏
2. 그리고 각 변수를 초기화 한 뒤,
3. 오른쪽 포인터로 문자를 하나씩 넣고
4. freq[ch] += 1로 빈도를 갱신한다.
5. 어떤 문자가 3회가 되는 순간, 왼쪽 포인터를 이동시키며 freq[s[left]] -= 1를 반복해 다시 2회 이하로 만든다.
6. 매 단계에서 윈도우 길이 right - left + 1로 최댓값을 갱신한다.

---

이렇게 해서 조건(각 문자는 최대 2회)을 항상 유지하며 O(n)에 답을 구한다.

🐋정답코드🐋

from collections import defaultdict

class Solution(object):
    def maximumLengthSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
    	
        freq=defaultdict(int)	# 각 문자의 빈도 계산
        left=0	# 윈도우의 왼쪽 경계
        best=0	# 정답(최대 길이)
        
        for right,char in enumerate(s):
        	freq[char]+=1
            
            while freq[char]>2:	# 방금 추가한 ch가 3회 이상이면, 2회가 될 때까지 left를 이동
            	freq[s[left]]-=1
                left+=1
            
            best=max(best,left+right-1)
            
        return best