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).
Example:
Input: S = "ADOBECODEBANC", T = "ABC" Output: "BANC"
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.
class Solution { public: string minWindow(string s, string t) { if (t.size() > s.size()) return ""; unordered_map<char, int> cnt; for (char c : t) cnt[c]++; int start = -1, min_len = INT_MAX; int l = 0, r = 0; int match = 0; while (r < s.size()){ cnt[s[r]]--; if (cnt[s[r]] >= 0) match++; while (match == t.size()){ if (r-l+1 < min_len){ start = l; min_len = r-l+1; } cnt[s[l]]++; if (cnt[s[l]] > 0) match--; l++; } r++; } return min_len == INT_MAX ? "" : s.substr(start, min_len); } };