[Leetcode 아주 상세한 문제풀이] 76. Minimum Window Substring - 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 76번 문제 Minimum window substring 이다.

우선 문제를 살펴보자.

 

리트코드 76번 문제 Minimum window substring 링크

Minimum Window Substring - LeetCode

Minimum Window Substring - LeetCode

 

Given two strings s and t of lengths m and n respectively, return the minimum window substring  of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique.

 

Example 1:
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.
Example 2:
Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.
Example 3:
Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.
 

Constraints:
m == s.length
n == t.length
1 <= m, n <= 105
s and t consist of uppercase and lowercase English letters.
 

Follow up: Could you find an algorithm that runs in O(m + n) time?

 

 

문제 설명

문제에 대해 간략히 살펴보자. 인풋으로 두 개의 문자열 s와 t가 주어진다. 이때 문자열 s와 t의 길이는 각각 m과 n이다. 이때 문자열 t를 포함할 수 있는 가장 작은 substring window를 문자열 s에서 찾아내는 문제다.

문제 예시 1번에서 처럼 s = "ADOBECODEBANC", t = "ABC"가 주어졌다고 생각해 보자. 이때 문자열 s에서 "ABC"가 모두 포함되는 가장 짧은 substring은 "BANC"가 됨을 알 수 있다. Substring을 찾는 문제이기 때문에 연속된 문자열이어야 한다. 하지만 t에 해당하는 문자열이 순서대로 있을 필요는 없다. 따라서 "BANC"라는 substring 안에 t에 해당하는 문자 "ABC"가 모두 존재하기 때문에 이를 찾아내면 된다.

 

 

문제 접근법

이 문제를 해결하기 위해서는 Sliding window 문제와 비슷하게 접근해야 한다.

우리는 문자열 t를 포함하는 '최소' 길이의 substring을 문자열 s에서 찾아야 한다.

따라서 이를 탐색하기 위해서 두 개의 포인터를 만들어 줄 것이다.

이를 left 포인터 (L_P)와 right 포인터 (R_P)라고 하자.

우선 두개의 포인터를 문자열 s의 가장 왼쪽에 위치해 놓는다.

그리고 right 포인터를 한 칸씩 오른쪽으로 옮겨간다.

이때 left 포인터와 right 포인터 사이에 문자열 t에의 문자들이 있는지 확인한다.

가장 처음 탐색되는 경우는 아래와 같이 left 포인터가 첫번째 A right 포인터가 6번째 C를 가리키고 있을때다.

이때 문자열 t의 "ABC"가 모두 포함되며 이때 substring의 길이는 6 (="ADOBEC")이다.

 

비록 문자열 t가 모두 포함되는 substring을 찾았지만 우리가 찾고자 하는 것은 '최소' 길이의 substring이다.

문자열 s안에 문자열 t를 포함하는 더 잛은 substring을 탐색해 봐야 한다.

다음 탐색을 위해서는 left 포인터를 오른쪽으로 옮겨야 한다.

Left 포인터를 오른쪽으로 한 칸 옮긴 뒤 처음 경우와 같이 right 포인터를 오른쪽으로 옮기며 탐색한다.

이 과정에서 문자열 t가 모두 포함되는 substring을 또 찾을 수도 있다.

우리는 '최소' 길이의 substring을 찾아야 하므로 앞서 찾은 substring과 길이 비교를 해두어야 한다.

두 개의 포인터를 옮기는 과정을 반복하다보면 right 포인터가 가장 오른쪽에 다다른다.

이때 left 포인터를 현재 위치에서 오른쪽으로 마지막 탐색을 진행하면 된다.

이 문제 예시의 경우 left pointer가 B 그리고 right 포인터가 C에 있을 경우,

문자열 t를 포두 포함하며 길이가 가장 짧은 (=4) substring이 된다.

이제 이 과정을 코드로 구현해 보자.

 

 

문제 풀이

두 개의 문자열 s와 t를 입력받을 함수를 정의해 준다. (line 1)

우리는 defaultdict class를 collections module에서 불러올 것이다. (line 2)

이는 각 문자열 s와 t의 문자 빈도를 기억해두기 위함이다.

우선 입력받은 두 문자열의 문자 빈도를 기억하기 위한 dictionary를 int로 초기화 해준다. (line5-6)

우리가 탐색하고자 하는 것은 문자열 t가 문자열 s안에 들어있는지다.

그렇기 때문에 우선 문자열 t에 들어있는 문자 빈도를 dictionary에 기억해둔다. (line 7-8)

앞서 설명한대로 left와 right 포인터를 만들어 인덱스 값 0으로 초기화를 해준다. (line 11)

그리고 substring의 '최소' 길이를 추적할 변수를 무한대 (inf)로 설정해준다. (line 12-13)

만약 최소 길이의 substring을 찾는다면 이 값은 특정 값으로 업데이트 된다.

따라서 최종적으로 이 값이 무한대일 경우 최소 길이의 substring을 못찾았다는 얘기가 된다.

추가로 문자열 t의 길이도 확인해준다. (line 14)

우선 right 포인터의 위치가 문자열 s보다 앞쪽일 경우 탐색을 진행한다. (line 17)

만약 right 포인터가 문자열 s에서 가리키는 문자가 문자열 t의 dictionary에 있다면,

문자열 s의 dictionary에서 그 문자에 해당하는 값을 하나 올려준다. (line 19-20)

만약 right 포인터가 가리키는 문자열이 s와 t의 dictionary에서 같은 값을 갖는다면,

이는 곧 그 문자의 개수가 같다는 뜻이므로 문자열 개수를 카운트 하기 위한 변수에 1을 더해준다. (line 21-22)

그리고 마지막 과정을 마친 후 right 포인터를 오른쪽으로 한 칸 옮겨주며 탐색을 계속한다. (line 39)

위 과정을 반복하다 보면 어느 순간 left 포인터와 right 포인터 사이에 substring에서

문자열 t가 문자열 s에 포함되는 순간을 만나게 된다.  (line 25)

이 경우가 바로 우리가 찾고있는 경우인데 앞서 설명한데로 '최소' substring을 찾는 것이 목표다.

따라서 이때 window 크기를 확인해야만 한다. (line 26)

 

만약 지금까지 찾은 최소 window 크기보다 작다면

만약 그 window 크기가 지금까지 찾은 최소 window 크기보다 작다면 (line 27)

최소 window 크기를 업데이트 해주고 동시에 left 포인터를 min_start에 저장해둔다. (line 28-29)

그리고 left 포인터가 가리키는 문자열 s의 문자가 문자열 t의 dictionary에 존재한다면 (line 30)

문자열 s의 dictionary에서 그 문자에 해당하는 값을 하나 줄여준다. (line 31)

그리고 카운트 하고 있는 변수도 1을 줄여준다. (line 32-33)

마지막으로 left 포인터를 오른쪽으로 한 칸 옮겨준다. (line 36)

이 과정은 앞서 설명한대로 다른 window를 찾기 위하여 현재 탐색하고 있는 window 크기를 줄이는 과정이다.

최종적으로 최소 substring 길이가 아직 무한대 (inf) 값이라면 그 substring을 찾지 못한 것이므로 아무것도 리턴하지 않는다.

하지만 최소 substring이 특정 값을 같는다면 문자열 t가 문자열 s에 포함되는 최소 길이의 substring을 찾았다는 얘기다.

따라서 이 경우 앞서 저장해 준 최소 substring의 처음 인덱스부터 거기에 최소 substring 길이를 더한 인덱스에 해당하는 문자를 출력하고 종료한다. (line 41)

 

 

문제 풀이 코드

def min_window(s, t):
    from collections import defaultdict
 
    # Initialize the dictionaries
    dict_t = defaultdict(int)
    dict_s = defaultdict(int)
    for char in t:
        dict_t[char] += 1
 
    # Initialize pointers and other variables to track the minimum window
    left, right = 0, 0
    min_len = float('inf')
    min_start = 0
    required_chars = len(dict_t)
    formed_chars = 0
 
    while right < len(s):
        # Expand the window
        if s[right] in dict_t:
            dict_s[s[right]] += 1
            if dict_s[s[right]] == dict_t[s[right]]:
                formed_chars += 1
 
        # Contract the window and move the left pointer to the right
        while left <= right and formed_chars == required_chars:
            window_len = right - left + 1
            if window_len < min_len:
                min_len = window_len
                min_start = left
 
            if s[left] in dict_t:
                dict_s[s[left]] -= 1
                if dict_s[s[left]] < dict_t[s[left]]:
                    formed_chars -= 1
 
            left += 1
 
        # Move the right pointer to the right
        right += 1
 
    return "" if min_len == float('inf') else s[min_start:min_start + min_len]
 
# Test cases
print(min_window("ADOBECODEBANC", "ABC"))  # Output: "BANC"
print(min_window("a", "a"))                # Output: "a"
print(min_window("a", "aa"))               # Output: ""