LeetCode Minimum Swaps to Group All 1's Together Solution
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 1:
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.
Example 2:
Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.
Example 3:
Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.
Constraints:
m == s.length
n == t.length
1 <= m, n <= 105
s
andt
consist of uppercase and lowercase English letters.
Follow up: Could you find an algorithm that runs in O(m + n)
time?
Problem Link: https://leetcode.com/problems/minimum-window-substring/
Solution
We will use a sliding window to find the minimum window.
We wish to use a charmap
to store the number of characters seen in s
, and we will use two indices to represent an interval (left inclusive, right exclusive) of the window
.
To ensure that all characters in t
is included, we can initialize charmap
to negative counts for each character in t
, so that when we iterate s
and increase the counter for each c
, we know that charmap[c] >= 0
means that s
contains enough c
to satisfy the condition.
So the window is valid when every value in charmap
is non-negative, thus we can find the smallest window.
Notice that our window interval is initialized with (-m, 0)
which has a length m
but will produce ""
if we were to obtain s[-m:0]
.
Implementation
1def minWindow(self, s: str, t: str) -> str:
2 m, n = len(s), len(t)
3 if m < n:
4 return ""
5 charmap = defaultdict(int)
6 for c in t:
7 charmap[c] -= 1
8 window, l = (-m, 0), 0
9
10 for r in range(m):
11 charmap[s[r]] += 1
12 r += 1
13 while min(charmap.values()) >= 0: # valid
14 if window[1] - window[0] >= r - l: # smaller than current
15 window = (l, r)
16 charmap[s[l]] -= 1
17 l += 1
18
19 return s[window[0] : window[1]]