Minimum window substring#
Practice Link#
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).
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.
Example#
1Input: S = "ADOBECODEBANC", T = "ABC"
2Output: "BANC"Thinking#
- Can this have a sliding window based approach?
Python Solution#
1from collections import Counter
2
3
4class Solution(object):
5 def minWindow(self, s, t):
6 """
7 :type s: str
8 :type t: str
9 :rtype: str
10 """
11
12 if not t or not s:
13 return ""
14
15 # Dictionary which keeps a count of all the unique characters in t.
16 dict_t = Counter(t)
17
18 # Number of unique characters in t, which need to be present in the desired window.
19 required = len(dict_t)
20
21 # left and right pointer
22 l, r = 0, 0
23
24 # formed is used to keep track of how many unique characters in t are present in the current window in its desired frequency.
25 # e.g. if t is "AABC" then the window must have two A's, one B and one C. Thus formed would be = 3 when all these conditions are met.
26 formed = 0
27
28 # Dictionary which keeps a count of all the unique characters in the current window.
29 window_counts = {}
30
31 # ans tuple of the form (window length, left, right)
32 ans = float("inf"), None, None
33
34 while r < len(s):
35
36 # Add one character from the right to the window
37 character = s[r]
38 window_counts[character] = window_counts.get(character, 0) + 1
39
40 # If the frequency of the current character added equals to the desired count in t then increment the formed count by 1.
41 if character in dict_t and window_counts[character] == dict_t[
42 character]:
43 formed += 1
44
45 # Try and contract the window till the point where it ceases to be 'desirable'.
46 while l <= r and formed == required:
47 character = s[l]
48
49 # Save the smallest window until now.
50 if r - l + 1 < ans[0]:
51 ans = (r - l + 1, l, r)
52
53 # The character at the position pointed by the `left` pointer is no longer a part of the window.
54 window_counts[character] -= 1
55 if character in dict_t and window_counts[character] < dict_t[
56 character]:
57 formed -= 1
58
59 # Move the left pointer ahead, this would help to look for a new window.
60 l += 1
61
62 # Keep expanding the window once we are done contracting.
63 r += 1
64 return "" if ans[0] == float("inf") else s[ans[1]:ans[2] + 1]