[리트코드] 3090 - Maximum Length Substring With Two Occurrences

3090. Maximum Length Substring With Two Occurrences

Easy

---

Given a string s, return the maximum length of a substring such that it contains at most two occurrences of each character.  

Example 1:

Example 2:

 

Constraints:

• 2 <= s.length <= 100
• s consists only of lowercase English letters.

분류

해시 테이블, 문자열, 슬라이딩 윈도우

---

문제 풀이

문제 분석

주어진 문자열 s에서 각 문자가 최대 2번 이하로 등장하는 가장 긴 부분 문자열(substring)의 길이를 구하는 문제입니다.

• 입력: 소문자 알파으로만 이루어진 문자열 s (길이 2 ~ 100)
• 출력: 조건(각 문자 최대 2회 등장)을 만족하는 부분 문자열 중 최대 길이 (정수)
• 심 제약: 부분 문자열 내 모든 문자의 빈도수가 2 이하여야 합니다.

---

접근 방법

이 문제는 슬라이딩 도우(Sliding Window, 두 포인터) 알고리즘과 **해시 (Hash Map)**을 조합하여 해결합니다.

• 슬라이딩 도우 선택 이유: "연속된 부분 문자열" 중 조건을 만족하는 최대 길이를 구하는 전형적인 문제 유형입니다. 도우의 오른쪽 경계를 확장하다가 조건을 위반하면 왼쪽 경계를 좁혀가며 유효한 구간을 유지합니다.
• 해시 (defaultdict) 선택 이유: 현재 도우 내에 포함된 각 문자의 등장 수를 O(1) 시간에 기록하고 확인하기 위해 사용합니다. 알파 소문자만 들어오므로 크기 26의 배열을 써도 무방하지만, 해시 이 구현이 더 간결합니다.
• 알고리즘 흐름:
  1. 오른쪽 포인터(right)를 한 칸씩 오른쪽으로 이동하며 도우를 확장합니다.
  2. 새로 들어온 문자의 개수가 2를 초과하면, 왼쪽 포인터(left)를 오른쪽으로 이동하며 도우를 축소하여 조건을 복구합니다.
  3. 매 단계마다 유효한 도우의 최대 길이를 신합니다.

---

구현 설명

1. 변수 초기화 및 도우 설정

• n = len(s): 문자열의 전체 길이 저장
• k = 2: 허용되는 최대 등장 수 상수화
• left = 0, right = 0: 도우의 시작과 끝을 가리키는 두 포인터 초기화 (초기 도우는 빈 구간 [0, 0))
• counts = defaultdict(int): 현재 도우 내 문자별 등장 수를 저장할 해시
• answer = 0: 정답(최대 길이)을 저장할 변수

2. 오른쪽 포인터 확장 루프 (while right != n)

• right가 문자열 끝(n)에 도달할 때까지 반복합니다.
• 문자 추가: counts[s[right]] += 1로 현재 오른쪽 문자를 도우에 포함시키고 개수를 증가시니다.

3. 조건 위반 시 왼쪽 포인터 축소 (while counts[s[right]] > k)

• 방금 추가한 문자 s[right]의 개수가 k(2)를 초과했다면 조건 위반 상태입니다.
• 도우 축소: counts[s[left]] -= 1로 왼쪽 문자를 도우에서 제거하고, left += 1로 왼쪽 경계를 오른쪽으로 한 칸 이동시니다.
• 이 과정을 s[right]의 개수가 2 이하가 될 때까지 반복하여 유효한 도우 상태로 만듭니다.

4. 정답 신 및 포인터 이동

• right += 1: 오른쪽 포인터를 다음 위치로 이동시니다 (도우 범위는 [left, right)).
• answer = max(answer, right - left): 현재 유효한 도우의 길이(right - left)와 기존 최대 길이 중 큰 값으로 정답을 신합니다.
• 루프 종료 후 answer 반환.

---

복잡도 분석

• 시간 복잡도: O(N)

  • right 포인터는 0부터 N-1까지 최대 한 번씩만 오른쪽으로 이동합니다.
  • left 포인터 역시 0부터 N-1까지 최대 한 번씩만 오른쪽으로 이동합니다.
  • 각 포인터가 문자열 길이 N만큼만 이동하므로 전체 연산 수는 2N에 비례합니다. 해시 연산(접근, 수정)은 평균 O(1)입니다.

• 공간 복잡도: O(1) 또는 O(알파 종류 수)

  • counts 해시 에는 최대 26개의 소문자 키만 들어갈 수 있습니다. 입력 크기 N에 비례하지 않고 상수 크기로 고정니다.

---

핵심 포인트

1. 슬라이딩 도우의 확장/축소 조건 명확화: 오른쪽 포인터는 무조건 확장하고, 조건을 위반하는 순간(특정 문자 카운트 > 2)에만 왼쪽 포인터를 축소합니다. 이 방식이 O(N)을 보장합니다.
2. while 루프 중으로 유효성 보장: if가 아닌 while을 사용하여 왼쪽 포인터를 이동시키는 이유는, 왼쪽 포인터를 한 칸 옮겼음에도 여전히 조건을 위반할 수 있기 때문입니다(예: aaa에서 오른쪽이 마지막 a를 가리킬 때, 왼쪽을 한 칸 옮기면 aa가 되어 여전히 위반).
3. 도우 범위 정의의 일관성: 코드에서 도우는 [left, right) (left 포함, right 미포함) 형태로 관리니다. right를 증가시킨 후 길이를 right - left로 계산하는 것이 이 정의와 일치합니다.

풀이 코드

class Solution:
    def maximumLengthSubstring(self, s: str) -> int:
        n = len(s)
        k = 2
        left = 0
        right = 0
        counts = defaultdict(int)
        answer = 0

        while right != n:
            counts[s[right]] += 1
            while counts[s[right]] > k:
                counts[s[left]] -= 1
                left += 1

            right += 1
            answer = max(answer, right - left)

        return answer