Description

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).

Example:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Note:

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

Solutions

1. Two Pointers

# Time: O(n)
# Space: O(n)
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        hash_map = collections.defaultdict(int)
        for ch in t:
            hash_map[ch] += 1
        # hash_map = collections.Counter(t)
        l, r = 0, 0
        min_window = ''
        cnt = len(t)
        
        for r in range(len(s)):
            # If we see a target letter, decrease the total target letter count
            if hash_map[s[r]] > 0:
                cnt -= 1
            
            # Decrease the letter count for the current letter
			# If the letter is not a target letter, the count just becomes -ve
            hash_map[s[r]] -= 1

            # If all letters in the target are found:
            while cnt == 0:
                win_size = r - l + 1
                if not min_window or win_size < len(min_window):
                    # Note the new minimum window
                    min_window = s[l:r+1]
                # Increase the letter count of the current letter
                hash_map[s[l]] += 1

                # If all target letters have been seen and now, a target letter is seen with count > 0
				# Increase the target length to be found. This will break out of the loop
                if hash_map[s[l]] > 0:
                    cnt += 1
                l += 1
        return min_window

# 268/268 cases passed (88 ms)
# Your runtime beats 92.35 % of python3 submissions
# Your memory usage beats 61.11 % of python3 submissions (13.4 MB)

References

  1. 76. Minimum Window Substring
  2. Substring 总结