MIn sliding Window
unknown
plain_text
a year ago
1.1 kB
1
Indexable
Never
#include <bits/stdc++.h> using namespace std; string minWindow(string s, string t) { unordered_map<char,int> ms; unordered_map<char,int> mt; if(s.length()<t.length()) return ""; for(int i=0;i<t.length();i++){ mt[t[i]]++; } int count=0, start=0, start_ind=-1, min_length=INT_MAX; for(int i=0; i<s.length(); i++){ ms[s[i]]++; if(ms[s[i]] <= mt[s[i]]) count++; if(count == t.length()){ while(ms[s[start]] > mt[s[start]]){ ms[s[start]]--; start++; } if(min_length>i-start+1){ min_length = i-start+1; start_ind = start; } } } if(start_ind == -1) return ""; else return s.substr(start_ind , min_length); } int main() { string s, t; cin>>s>>t; string ans = minWindow(s, t); cout<<ans<<endl; return 0; }