LeetCode 76. Minimum Window Substring

파이썬 알고리즘 인터뷰 76번(리트코드 76번) Minimum Window Substring
https://leetcode.com/problems/minimum-window-substring/

나의 풀이

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        char_checked = set()
        char_count_t = collections.Counter(t)
        num_of_char = len(char_count_t.keys())
        char_count_s = collections.defaultdict(int)

        i = 0
        left = None
        while len(char_checked) < num_of_char:
            if i == len(s):
                return ""
            if s[i] in char_count_t:
                if left is None:
                    left = i
                right = i
                char_count_s[s[i]] += 1
                if char_count_s[s[i]] == char_count_t[s[i]]:
                    char_checked.add(s[i])
            i += 1
        while char_count_s[s[left]] > char_count_t[s[left]]:
            char_count_s[s[left]] -= 1
            left += 1
            while s[left] not in char_count_t:
                left += 1
        
        result = s[left:right + 1]
        
        while i < len(s):
            if s[i] in char_count_t:
                char_count_s[s[i]] += 1
                while char_count_s[s[left]] > char_count_t[s[left]]:
                    char_count_s[s[left]] -= 1
                    left += 1
                    while s[left] not in char_count_t:
                        left += 1
                if i - left + 1 < len(result):
                    result = s[left: i + 1]
            i += 1

        return result

• 속도는 빠른 편이나 가독성이 좋지 않다. while문이 너무 많다.

다른 풀이1

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

        char_count_t = collections.Counter(t)
        char_count_s = collections.Counter()
        required = len(char_count_t)
        formed = 0

        left = 0
        min_length = float('inf')
        min_window = ""

        for right in range(len(s)):
            char = s[right]
            if char in char_count_t:
                char_count_s[char] += 1
                if char_count_s[char] == char_count_t[char]:
                    formed += 1
            
            while formed == required:
                if right - left + 1 < min_length:
                    min_length = right - left + 1
                    min_window = s[left:right+1]

                left_char = s[left]
                if left_char in char_count_t:
                    char_count_s[left_char] -= 1
                    if char_count_s[left_char] < char_count_t[left_char]:
                        formed -= 1

                left += 1

        return min_window

• GPT가 나의 풀이의 가독성을 개선해주었다.
• 속도는 느려졌다.

다른 풀이2

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

        char_count_t = collections.Counter(t)
        required = len(t)

        left = 0
        min_length = float('inf')
        min_window = ""
        count = 0  # 현재 윈도우 내 t의 문자가 충족된 개수

        for right, char in enumerate(s):
            if char in char_count_t:
                if char_count_t[char] > 0:
                    count += 1
                char_count_t[char] -= 1

            while count == required:  # 모든 문자가 포함됨
                if right - left + 1 < min_length:
                    min_length = right - left + 1
                    min_window = s[left:right+1]

                if s[left] in char_count_t:
                    char_count_t[s[left]] += 1
                    if char_count_t[s[left]] > 0:
                        count -= 1

                left += 1  # 윈도우 축소

        return min_window

다른 풀이3

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

        need = Counter(t)  # 필요한 문자 개수
        missing = len(t)   # 남은 필요 문자 개수
        left = start = end = 0
        
        for right, char in enumerate(s, 1):  # right는 1부터 시작 (슬라이싱 편의)
            if need[char] > 0:
                missing -= 1
            need[char] -= 1  # 윈도우에 포함된 문자 수 감소
            
            if missing == 0:  # 모든 문자가 포함됨
                while need[s[left]] < 0:  # 불필요한 문자 제거
                    need[s[left]] += 1
                    left += 1
                
                if end == 0 or right - left < end - start:  # 최소 길이 갱신
                    start, end = left, right
            
                need[s[left]] += 1  # left 증가로 인해 한 문자 제거됨
                missing += 1
                left += 1
        
        return s[start:end]

• 가장 정석적이고 빠르다.
• need Couter에 t에 없는 문자를 넣을 생각을 못했다. 내 풀이 보다 메모리는 좀 더 쓰게 되겠지만 코드가 간결해진다.

다른 풀이4

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        t_count = collections.Counter(t)
        current_count = collections.Counter()
        start = float('-inf')
        end = float('inf')
        left = 0

        for right, char in enumerate(s, 1):
            current_count[char] += 1

            while current_count & t_count == t_count:
                if right - left < end - start:
                    start, end = left, right
                current_count[s[left]] -= 1
                left += 1
        
        return s[start:end] if end - start <= len(s) else ''

• 두 Counter의 & 연산을 이용해서 보기엔 멋있으나 느리다.

배운 점

• 두 Counter끼리 & 연산을 할 수 있다.