aqws, C++ (gcc) - rextester

aqws

class Solution {
public:
    //order of the number of distinct characters in b
    bool same(unordered_map<char, int>& a, unordered_map<char, int>& b)
    {
        if(a.size() < b.size()) return false;
        for(auto it = b.begin(); it != b.end() ;it++)
            if( (a.find(it->first) == a.end()) || (a[it->first] < it->second) ) return false;
        return true;
    }
    string minWindow(string s, string t) {
        string st = "";
        int l1 = t.length(), l = s.length();
        if(l<l1)                return st;
        
        unordered_map<char,int>findr; // map for chars and theri frquency in the string being searched for
        for(int i=0;i<l1;i++) // O(l1)
            if(findr.find(t[i]) == findr.end()) findr.insert({t[i],1}); 
            else    findr[t[i]]++;
        
        vector<int>key;//O(l)      // which is the next valid jump position for the front pointer
        for(int i=0;i<l;i++)    if( findr.find(s[i]) != findr.end() )   key.push_back(i);  
        
        if(key.size() == 0)     return st;
        int ptr1 = key[0], ptr2 = key[0], ans, min = l+1;
        unordered_map<char,int>match;// shall store the chars and frequency for current window
        
        int left=0, right=-1;
        while( ptr1<l && ptr2<l )
        {
            if(ptr2 < ptr1)   ptr2 = ptr1;// ptr2 never stays behind ptr1 
            
            if( findr.find(s[ptr2]) != findr.end() )
            {
                if( match.find(s[ptr2]) == match.end() )    match.insert({s[ptr2],1});
                else                                        match[ s[ptr2] ]++;
                
                if( same(match, findr) )
                {
                    ans = ptr2 - ptr1 + 1;
                    if(ans < min) {     min = ans; left = ptr1; right = ptr2;   }
                    
                    match[ s[ptr1] ]--;
                    char last = s[ptr1];
                    if(match[s[ptr1]] <= 0) match.erase(match.find(s[ptr1]));
                    if(key.size())  key.erase(key.begin());
                    if(key.size() > 0)  ptr1 = key[0];   
                    else   break;
                    while( match[last] >= findr[last] ) // ptr1 is moving forward continously; ptr2 stays the same
                    {
                        ans = ptr2 - ptr1 + 1;
                        if(ans <= min) {     min = ans; left = ptr1; right = ptr2;   }
                        last = s[ptr1];
                        match[ s[ptr1] ]--;
                        if(match[s[ptr1]] <= 0) match.erase(match.find(s[ptr1]));
                        if(key.size())  key.erase(key.begin());
                        if(key.size() > 0)  ptr1 = key[0];   
                        else   break;
                    }
                }
            }
            
            ptr2++; // must improve ptr2 at each step
        }
        if(right>=left)  st = s.substr(left, right-left+1); // O(length of answer time)
        return st;
    }
};


run \| edit \| history \| help	0