MIn sliding Window

mail@pastecode.io avatar
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;
}