76. Minimum Window Substring
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 “”.
Method 1 Sliding Window
- 2 pointers left and right point to the first element of string S.
- Use right to expand the window until it contains all of the characters of T.
- Use left to compress the window. If the window does not contain all characters of T, repeat Step 2.
- The result is the smallest window.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35string minWindow(string s, string t) {
int left = 0, right = 0;
unordered_map<char, int> ht;
string ans = "";
int size_ = INT_MAX;
for (int i = 0; i < t.size(); i++) {
ht[t[i]]++;
}
while (left < s.size() && right <= s.size()) {
string winStr = s.substr(left, right-left);
unordered_map<char, int> hs;
for (int j = 0; j < winStr.size(); j++) {
hs[winStr[j]]++;
}
vector<bool> boolArray(ht.size(), false);
int k = 0;
for (auto iter : ht) {
if (hs[iter.first] >= iter.second) {
boolArray[k++] = true;
} else {
boolArray[k++] = false;
}
}
if (all_of(boolArray.begin(), boolArray.end(), [](bool i){return i == true;})) {
if (winStr.size() < size_) {
ans = winStr;
size_ = ans.size();
}
left++;
} else {
right++;
}
}
return ans;
}
Method 2 Optimized Sliding Window
- Store string T in a Hash map letterCnt
- Traversal string S. If value - 1 >= 0, current letter is in T. cnt++. When cnt == t.size(), current window contains all letters of T. Enter the loop (Step 3 & 4).
- Then record the minimum substring length and its value.
- Move left ahead. If value + 1 > 0, a letter in T is missing. cnt–. Then left++.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18string minWindow(string s, string t) {
string res = "";
unordered_map<char, int> letterCnt;
int left = 0, cnt = 0, minLen = INT_MAX;
for (char c : t) letterCnt[c]++;
for (int i = 0; i < s.size(); i++) {
if (--letterCnt[s[i]] >= 0) cnt++;
while (cnt == t.size()) {
if (minLen > i - left + 1) {
minLen = i - left + 1;
res = s.substr(left, minLen);
}
if (++letterCnt[s[left]] > 0) cnt--;
left++;
}
}
return res;
}