8)Smallest window in a string containing all the characters of another string -(sliding window | variable size)

Given two strings S and P. Find the smallest window in the S consisting of all the characters of P.

Example 1:

Input:
S = "timetopractice"
P = "toc"
Output: 
toprac
Explanation: "toprac" is the smallest
substring in which "toc" can be found.

Example 2:

Input:
S = "zoomlazapzo"
P = "oza"
Output: 
apzo
Explanation: "apzo" is the smallest 
substring in which "oza" can be found.



c++ implementation:

string minWindow(string a, string p) 
    { 
        int n=a.length();
         int m=p.length();
        
        unordered_map<char,int>mp;
        for(int i=0;i<m;i++)
        mp[p[i]]++;
        
        int count=mp.size();
        
        int i=0;int j=0; int start=0;
        int len=INT_MAX;
        
        while(j<n)
        {
              mp[a[j]]--;
              if(mp[a[j]]==0)
              count--;
            
          if (count == 0) {
            while (count == 0) 
            {
                
                if (len > j - i + 1) {
                    len = min(len, j - i + 1);
                     start = i;
                }
 
                mp[a[i]]++;
                if (mp[a[i]] > 0)
                    count++;
 
                i++;
            }
          } 
            
           j++;   
        }
        if (len != INT_MAX)
        return a.substr(start, len);
        else
        return "";
        }
Time Complexity: O(n) 
space Complexity: O(n) 



darkmode