Description
Submission
class Solution {
public:
string minWindow(string s, string t) {
unordered_map<char, int> counter;
for(auto c : t) counter[c]++;
int l = 0, r = 0;
int minL = 0, minR = s.size();
int remaining = counter.size();
for(; r < s.size(); ++r) {
if(counter.find(s[r]) != counter.end()) {
counter[s[r]]--;
if(counter[s[r]] == 0) remaining--;
}
if(remaining == 0) {
// shrinking the window size by moving left forward
while(l < r) {
auto iter = counter.find(s[l]);
if(iter == counter.end()) {
l++;
} else if(iter->second < 0) counter[s[l++]]++;
else break;
}
if(r - l < minR - minL) {
minR = r;
minL = l;
}
// move the left forward
counter[s[l++]]++;
remaining++;
}
}
if(minR - minL == s.size()) return "";
return s.substr(minL, minR - minL + 1);
}
};
References
- https://www.youtube.com/watch?v=eS6PZLjoaq8