슬라이딩 윈도우 2 - Minimum Window Substring

76. Minimum Window Substring

https://leetcode.com/problems/minimum-window-substring/

---

Solution 1: Accepted (Runtime: 96 ms - 86.85% / Memory Usage: 14.7 MB - 98.54%)

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        need = collections.Counter(t)
        missing = len(t)
        left = start = end = 0

        # 오른쪽 포인터 이동
        for right, char in enumerate(s, 1):
            missing -= need[char] > 0
            need[char] -= 1

            # 필요 문자가 0이면 왼쪽 포인터 이동 판단
            if missing == 0:
                while left < right and need[s[left]] < 0:
                    need[s[left]] += 1
                    left += 1

                if not end or right - left <= end - start:
                    start, end = left, right
                need[s[left]] += 1
                missing += 1
                left += 1
        return s[start:end]

need: 찾아야할 문자의 종류와 개수 => t Counter
missing: 찾아야할 문자의 길이
start & end: 최종 minimum window 의 인덱스

문자 하나씩 보면서 그 문자의 need 값이 양수일 때만 missing - 1
(=> 찾아야될 문자일 때만 missing - 1)
지금 보고 있는 문자의 need 값은 -1

if missing == 0: )
찾아야할 문자를 모두 찾았으면 left 포인터 이동
while left < right and need[s[left]] < 0:
=> 불필요한 문자는 need 가 음수니까 pass 하도록 left + 1

더 짧은 길이로 start & end update

enumerate
: (index, value) 를 튜플 형태로 반환

enumerate(s, 1)
=> index 에 1 을 더함
실제 값은 [0 ~ len(s)-1] 의 값이지만 index 는 1 ~ len(s) 로 나타남

Solution 2: Accepted (Runtime: 1776 ms - 5.07% / Runtime: 1776 ms - 5.07%)

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

            # AND 연산 결과로 왼쪽 포인터 이동 판단
            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 ''

Solution 1 과 같은 방식이지만 문자 개수 Count 가 다름

current_count 도 만들어서 for 문으로 돌때마다 count 값 + 1

while current_count & t_count == t_count:
=> & 연산으로 t_count 가 포함되는지 확인하고 left 이동

훨씬 느리다