Problem Statement: Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string. 

Examples:

Example 1:
Input: s = "ADOBECODEBANC", t = "ABC" 
Output: 4  
Explanation: BANC has all required characters 

Example 2:
Input: s = "ABBXC", t = "BXC" 
Output: 3 
Explanation: BXC has all required characters 

Solution 

Disclaimer: Don’t jump directly to the solution, try it out yourself first. 

Brute Force Solution : 

We will take 2 maps to store the frequency of the characters, mp1 contains the frequency of characters required, and mp2 will contain the frequency of characters we have currently in the window.

Ex - s= "adobecodebanc" , t="abc" 
Mp1 a :1 b:1 c:1 Mp2 a:1 

• Now we start iterating in s from i=0,j=0, and if s[j] is present in mp1 , we add s[j] in mp2.  increment j.
• Now s[j] is d, not required, we move on.
• When j==t.size(), there is a possibility that we have our answer, so we check if mp2 has all the elements required by mp1 (for this we will have to iterate the whole map).
• When we reach j==5, we will see we do have everything required, so this could be possible.
• We update ans and move i++ and j=i.
• Now we will try to make another substr from j=1.
• At j=5, Now when we move j, s[j] is o, its d, and then e, when we get b, we first check if  mp2 has any value in it, i.e, between i and j till now have we found any required element. 
• If not, we will update i=j, add s[j] to mp2 and repeat. 

Code:

#include<bits/stdc++.h>

#include<iostream>

using namespace std;
bool check(map < char, int > mpt, map < char, int > mps) {
  for (auto i: mpt) {
    if (mps.find(i.first) == mps.end()) return false;
    if (mps[i.first] < i.second) return false;
  }
  return true;
}
string makeString(int i, int j, string s) {
  string str = "";
  while (i <= j) {
    str += s[i];
    i++;
  }
  return str;
}
string minWindow(string s, string t) {
  map < char, int > mpt;
  map < char, int > mps;
  for (int i = 0; i < t.length(); i++) {
    mpt[t[i]]++;
  }
  int i = 0, j = 0;
  int ans = INT_MAX;
  string str = "";
  while (j < s.length()) {
    if (mpt.find(s[j]) != mpt.end()) {
      if (mps.size() == 0) i = j;
      mps[s[j]]++;
    }
    if (j - i + 1 >= t.length()) {
      bool f = check(mpt, mps);
      if (f) {
        mps.clear();
        if (ans > j - i + 1) {
          str = makeString(i, j, s);
          ans = j - i + 1;
        }
        j = i + 1;
        i = j;
        continue;
      }
    }
    j++;
  }
  return str;
}
int main() {
  string s = "adobecodebanc", t = "abc";
  cout << "The minimum window is: " << minWindow(s, t);
  return 0;
}

OPTIMAL SOLUTION 

Let’s try to create a sliding window and, remove the O(n), it was taking to match both maps every time. 

For that we will take 2 variables, current, which will tell us how many characters we have in mps, that are required, and another variable total tells us how many totals are required. 

• We start at i=0 and j=0. We check if the element we are at is required, and we add it to mps. 
• Now we have a val that was needed, so cur++, and check if(cur=total) this tells us if we need to find more elements. 

Note: we only update cur if mps[ele]=mpt[ele], not greater case because even if we have more, we only require mpt[ele]. 

• Now j is d, o then b. b is required, add it to map, update cur, cur still != total.
• Moving ahead at index 5 we will get j as c, and cur=total, this could be a possible answer.
• Store the indices of I,j as that is a possible answer string as well as update res, for future comparisons. 
• Now, it’s time to slide the window, we will move i till cur!=total because to get a better answer, we first need to let go of this one.
• Also at every step, we keep checking on the res,  because removing unnecessary elements from between could possibly affect the length. In the end, we build strings from the indices we have. 

Code:

#include<bits/stdc++.h>

#include<iostream>

using namespace std;
string minWindow(string s, string t) {
  if (t.length() == 0) return "";
  map < char, int > mpt;
  map < char, int > mps;
  for (int i = 0; i < t.length(); i++) {
    mpt[t[i]]++;
  }
  int cur = 0, total = mpt.size();
  int i = 0, j = 0;
  int res = INT_MAX;
  pair < int, int > indices;
  while (j < s.length()) {
    if (mpt.find(s[j]) != mpt.end()) mps[s[j]]++;
    if (mpt.find(s[j]) != mpt.end() && mps[s[j]] == mpt[s[j]]) cur++;

    while (cur == total) {
      //update result 
      if (j - i + 1 < res) {
        res = j - i + 1;

        indices = make_pair(i, j);
      }
      //shrink 
      if (mps.find(s[i]) != mps.end()) {
        mps[s[i]]--;
        if (mps.find(s[i]) != mps.end() && mps[s[i]] < mpt[s[i]]) cur--;
      }
      i++;
    }
    j++;
  }
  if (res == INT_MAX) return "";
  string str = "";
  for (int i = indices.first; i <= indices.second; i++) {
    str += s[i];
  }
  return str;
}
int main() {
  string s = "adobecodebanc", t = "abc";
  cout << "The minimum window is: " << minWindow(s, t);
  return 0;
}

Special thanks to Rishika Gupta for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article. If you want to suggest any improvement/correction in this article please mail us at [email protected]