LeetCode 76 - Minimum Window Substring

문자열 s와 t가 주어졌을 때, t의 모든 문자를 포함하는 s의 가장 짧은 연속 부분 문자열(Substring)을 구하는 Hard 문제다. 두 개의 빈도수 해시맵과 have/need 조건을 추적하는 가변 길이 슬라이딩 윈도우(Sliding Window) 알고리즘으로 O(S + T) 선형 시간에 해결했다.

문제 링크 & 설명

문제 링크: 76. Minimum Window Substring
요약: 문자열 s에서 t에 포함된 모든 문자(중복 개수 포함)를 포함하는 가장 짧은 부분 문자열을 반환한다. 그러한 구간이 없다면 빈 문자열 ""을 반환한다.

매 단계마다 윈도우 안의 모든 문자 빈도를 일일이 비교하면 비효율적이다. t에 필요한 고유 문자 종류의 수를 need로 두고, 조건을 만족한 고유 문자의 수를 have로 관리하면 O(1) 시간에 윈도우의 유효성을 판단할 수 있다.

접근 방법

target_counts에 t의 문자 빈도를 저장하고, window_counts로 현재 윈도우 내 빈도를 기록한다.

target_counts = {}
for char in t:
    target_counts[char] = target_counts.get(char, 0) + 1

window_counts = {}
have = 0
need = len(target_counts)

res = [-1, -1]
res_len = float("inf")
left = 0

for right in range(len(s)):
    char = s[right]
    window_counts[char] = window_counts.get(char, 0) + 1

    if char in target_counts and window_counts[char] == target_counts[char]:
        have += 1

    while have == need:
        if (right - left + 1) < res_len:
            res = [left, right]
            res_len = right - left + 1

        left_char = s[left]
        window_counts[left_char] -= 1

        if (
            left_char in target_counts
            and window_counts[left_char] < target_counts[left_char]
        ):
            have -= 1

        left += 1

윈도우 확장: right 포인터를 오른쪽으로 이동하며 문자를 윈도우에 추가한다. 새로 들어온 문자의 빈도가 target_counts와 정확히 같아지는 순간 have += 1을 수행한다.
윈도우 축소: have == need가 되어 모든 필수 문자가 채워지면 현재 윈도우 길이로 최솟값을 갱신한다. 그다음 유효성이 깨질 때까지 left 포인터를 오른쪽으로 당기며 윈도우 크기를 줄인다.
유효성 감소: 빠지는 문자가 필수 문자이고 빈도가 요구량 미만으로 떨어지는 순간 have -= 1이 되어 while 루프를 빠져나온다.

복잡도 분석

시간 복잡도: O(S + T)
- t의 길이를 T, s의 길이를 S라 할 때, target_counts를 만드는 데 O(T)가 소요된다. 슬라이딩 윈도우에서 left와 right 포인터는 각각 s를 한 방향으로 최대 한 번씩만 지나가므로 전체 탐색은 O(S)에 종료된다.
공간 복잡도: O(S + T)
- 알파벳 빈도를 저장하는 해시맵에 최대 고유 문자 개수만큼 메모리가 사용된다.

구현 코드

class Solution:

    def minWindow(self, s: str, t: str) -> str:
        if not s or not t:
            return ""

        target_counts = {}
        for char in t:
            target_counts[char] = target_counts.get(char, 0) + 1

        window_counts = {}

        have = 0
        need = len(target_counts)

        res = [-1, -1]
        res_len = float("inf")
        left = 0

        for right in range(len(s)):
            char = s[right]
            window_counts[char] = window_counts.get(char, 0) + 1

            if char in target_counts and window_counts[char] == target_counts[char]:
                have += 1

            while have == need:
                if (right - left + 1) < res_len:
                    res = [left, right]
                    res_len = right - left + 1

                left_char = s[left]
                window_counts[left_char] -= 1

                if (
                    left_char in target_counts
                    and window_counts[left_char] < target_counts[left_char]
                ):
                    have -= 1

                left += 1

        l, r = res
        return s[l : r + 1] if res_len != float("inf") else ""

요약 및 회고

이 풀이의 핵심은 윈도우가 유효한 상태인지 판단할 때 매번 전체 해시맵을 순회하지 않고 have == need라는 단일 정수 조건으로 압축한 점이다. have의 증감이 문자 빈도가 정확히 경계선(target_counts[char])을 넘거나 미달할 때만 한 번씩 일어난다는 불변 조건을 설계해둠으로써 Hard 난이도 문제임에도 선형 시간에 깔끔하게 풀이할 수 있었다.