76. Minimum Window Substring

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity $O(n)$.

For example, S = "ADOBECODEBANC" T = "ABC" Minimum window is "BANC".

Note:

• If there is no such window in S that covers all characters in T, return the empty string "".
• If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

Solution: HashMap

import collections


class Solution(object):
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        target = collections.defaultdict(int)
        for char in t:
            target[char] += 1

        # indices of target characters
        indices = collections.deque()

        min_len = float('inf')
        remain = len(target)
        begin = end = 0

        for idx, char in enumerate(s):
            if char not in target:
                continue

            indices.append(idx)
            target[char] -= 1
            if target[char] == 0:
                remain -= 1

            while remain == 0:  # valid substring
                low = indices.popleft()
                if idx - low + 1 < min_len:
                    min_len = idx - low + 1
                    begin, end = low, idx + 1

                target[s[low]] += 1
                if target[s[low]] == 1:
                    remain += 1

        return s[begin: end]

Lessons:

• Use hash table to find out if we have used all characters from target. If we have used all, now we have a valid substring. Use while loop to remove the leftmost characters and find the minimum size, until the valid substring is invalid again.

Related:

• 340. Longest Substring with At Most K Distinct Characters