diff options
Diffstat (limited to 'other/min_window_substring.cpp')
-rw-r--r-- | other/min_window_substring.cpp | 37 |
1 files changed, 37 insertions, 0 deletions
diff --git a/other/min_window_substring.cpp b/other/min_window_substring.cpp new file mode 100644 index 0000000..c529687 --- /dev/null +++ b/other/min_window_substring.cpp @@ -0,0 +1,37 @@ +#include "leetcode.h" + +class Solution { +public: + string minWindow(string s, string t) { + unordered_map<char, int> m1, m2; + int check = INT_MAX; + string ans; + for (char &ch : t) + m1[ch]++; + int slow = 0, fast = 0, count = 0; + for (; fast < s.size(); fast++) { + char c = s[fast]; + if (m1.find(c) != m1.end()) { + m2[c]++; + if (m2[c] <= m1[c]) + count++; + } + if (count >= t.size()) { + while (m1.find(s[slow]) == m1.end() || m2[s[slow]] > m1[s[slow]]) { + m2[s[slow]]--; + slow++; + } + if (fast - slow + 1 < check) { + check = fast - slow + 1; + ans = s.substr(slow, check); + } + } + } + return ans; + } +}; + +int main() { + Solution obj; + cout << obj.minWindow("ADOBECODEBANC", "ABC"); +} |