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.
AC code:
class Solution { public: string minWindow(string s, string t) { map<char, int> m; for (int i = 0; i < t.length(); ++i) m[t[i]]++; int total = t.length(); int from = 0; int minn = INT_MAX; for (int i = 0, j = 0; i < s.length(); ++i) { if (m[s[i]]-- > 0) total--; while (total == 0) { if (i-j+1 < minn) { minn = i-j+1; from = j; } if (++m[s[j++]] > 0) total++; } } return (minn == INT_MAX) ? "" : s.substr(from, minn); } };
Runtime: 20 ms, faster than 45.51% of C++ online submissions for Minimum Window Substring.