(Python3) - LeetCode (Easy) : 3090. Maximum Length Substring With Two Occurrences

https://leetcode.com/problems/maximum-length-substring-with-two-occurrences

Maximum Length Substring With Two Occurrences - LeetCode

two pointer sweeping으로 푼 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

📑 왼쪽 포인터 l, 오른쪽 포인터 r, 정답 ans, 알파뱃을 key로 빈도수를 value 저장할 dict freq를 선언 후 적절히 초기화합니다.

📔 풀이과정

s의 부분문자열이란 s문자열 전체 혹은 일부로 이루어진 연속적인 문자열 이므로 부분문자열을 구성하는 각 알파벳의 빈도수가 최대 2 이하여야 합니다. 이를 검사하기 위해서는 다음을 진행합니다.

 

📑 s의 각 원소를 순서대로 순회하며 다음을 검사합니다
1. freq[s[r]]은 새로 확인할 알파뱃의 빈도수이므로 이 값 + 1로 갱신합니다

2. freq[s[r]]이 2를 초과하는 동안 freq[s[l]] -= 1 후 l+=1해줍니다

3. r을 1 증가시킨 뒤 현재 유효한 부분문자열의 길이는 r-l이 되며, 이를 ans와 비교해 최댓값을 갱신합니다.

 

s[r]을 빈도계산하기 전 이미 [l,r-1] 구간은 각 문자의 빈도수가 2이하인 유효한 부분문자열입니다. s[r]을 빈도계산해 갱신 후 2를 초과했을 때 2이하가 될때까지 s[l]을 이동하며 버린다면 갱신된 l1에 대해 다시 연속된 [l1,r] 구간의 유효한 부분문자열이 됩니다. 이때 갱신된 freq의 구성또한 이 부분문자열의 각 빈도수를 정확히 가지게 됩니다. 

 

📑 시간 복잡도

O(N): s배열 길이 N에 대해 r은 최대 N번 증가하고 l역시 최대 N번 증가하기 때문입니다.

 

📑 공간 복잡도

O(1): 소문자 알파뱃 만큼의 빈도수를 key로 가지기 때문입니다.

📔 정답 출력 | 반환

ans를 반환합니다.

---

📕 Code

📔 Python3

class Solution:
    def maximumLengthSubstring(self, s: str) -> int:
        l,r,ans = 0,0,0
        freq = {}
        while r < len(s):
            freq[s[r]] = freq.get(s[r],0) + 1
            while freq[s[r]] > 2:
                freq[s[l]] -= 1
                l += 1
            r += 1
            ans = max(ans, r-l)
        return ans

 

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.