LC076 - Minimum Window Substring

Problem

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

Input: s = "ADOBECODEBANC", t = "ABC"

Output: "BANC"

Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Solution

Use a hash map to compare number of target characters in current window to target. Progressively decrease window size and shift right after finding a match. This solution is done in linear $O(n)$ time and uses $O(t)$ extra space.

def minWindow(self, s: str, t: str) -> str:
	if t == "": 
		return ""

	req = {}
	cur = {}

	# Can use collections.Counter for this
	for char in t:
		if char in req:
			tmp = req[char]
			req[char] = tmp + 1
		else:
			req[char] = 1

	reqN = len(req)
	curN = 0

	res = [0,-1]
	resLen = math.inf

	left = 0
	for right in range(len(s)):
		char = s[right]

		if char in cur:
			tmp = cur[char]
			cur[char] = tmp + 1
		else:
			cur[char] = 1
		
		if char in req and cur[char] == req[char]:
			curN += 1

		# if window is smaller, then update smallest window size
		while reqN == curN:
			if (right - left + 1) < resLen:
				res = [left, right]
				resLen = (right - left + 1)
			# remove the leftmost char of current window
			cur[s[left]] -= 1
			if s[left] in req and cur[s[left]] < req[s[left]]:
				curN -= 1
			left += 1

	left, right = res

	if resLen != math.inf:
		return s[left:right+1]
	else:
		return ""