Strings: Minimum Window Substring

Problem Statement:

You are given 2 strings s1 and s2. You need to find the smallest substring in s1 that has all the characters of s2.

Example

Input: s = "ARTYUIBANC", t = "ABC"
Output: "BANC"

Solution

This problem can be solved by number of methods.

Method 1: Brute Force Approach

In this approach, generate all the sub strings of s1 and check if all the characters of s2 is present in that substring or not.

Then we print the smallest substring having all characters of s2.

Method 2: Sliding Window Approach.

In this approach, we will 2 pointers.”start”, “end”.
Initially we increment end pointer.
And get to the point where we have included all the characters from s2 in s1.

Then we start incrementing start pointer, so to shrink the gap.

 

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <stack>
#include <vector>
#include <unordered_set> 
#include <queue> 

using namespace std;

string min_window_substring(string s, string t) 
{
    //since there are 256 char, initialize it to 0
    std::vector<int> map(256, 0);
    
    // create count map for characters from t
    for (const auto c : t) 
    {
        map[c]++;
    }
    
    int count = t.length();
    
    int begin = 0;
    int end = 0;

    int minWindow = -1;
    int minWindowStart = -1;
    
    while (end < s.size()) {
 
        if (map[s[end]]-- > 0) {
            count --;
        }

        while (count == 0) {
            int curWindow = end - begin + 1;
            if ((minWindow == -1) || (curWindow < minWindow)) {
                minWindow = curWindow;
                minWindowStart = begin;
            }

            if (map[s[begin]]++ >= 0) {
                count ++;
            }
            begin++;
        }

        end++;
    }
    
    if (minWindow == -1) {
        return "";
    } else {
        return s.substr(minWindowStart, minWindow);
    }
}     

int main() 
{ 
      
string s1 = "ADOBECODEBANC"; 
string s2 = "ABC"; 
 
cout<<"The number of different integers are "<< min_window_substring(s1, s2)<<endl;

return 0; 
} 

Output:

The number of different integers are BANC

 

 

 

 

Write a Comment

Leave a Comment

Your email address will not be published. Required fields are marked *