Smallest window in a String containing all characters of other String

Given two strings string1 and string2, the task is to find the smallest substring in string1 containing all characters of string2.

Examples :

Input: string = “Cplusplus is the best”, pattern = “pp”
Output: Smallest window is : plusp
Explanation: 
“plusp” contains all the characters of pattern.

Input: string = “Cplusplus”, pattern = “Cpp”
Output: Smallest window is : Cplusp 

Approach :
The size of the smallest window lies in [ size_of_string2 , size_of_string1] both inclusive. Now ,we have a search space so,we can apply binary search here . For each size of window we check whether it contains all the characters of the string2 or not.

1. First check if the length of string is less than the length of the given pattern, if yes then “no such window can exist“.
2. Apply binary search . l= sizeof(string2) and r = sizeof(string1)+1.
3. Check if there exist any substring of size (l+r)/2 . If true then store the substring and update r = (l+r)/2 and if false update l = (l+r)/2 . Check until l < r.
4. Store the occurrence of characters of the given pattern in a hash_str2[].
5. Start matching the characters of string2 with the characters of string1 i.e. increment count if a character matches.
6. Check if (count == length of string2 ) this means a substring is found.

Implementation in C++:

// C++ program to find smallest window containing 
// all characters of a string using binary search. 
#include <bits/stdc++.h>
using namespace std;
string substring = "";
bool check(string str1, int hash_str2[], int window, int len2)
{
    int hash_str1[256] = {0};
    int count = 0;
    // store the occurrence of first window of size window 
    for (int i = 0; i < window; i++) {
        hash_str1[str1[i]]++;
        if (hash_str2[str1[i]] != 0 && hash_str1[str1[i]] <= hash_str2[str1[i]])
            count++;
    }
    //if all the characters of str1 and str2
    //matches then return true
    if (count == len2) {
        substring = str1.substr(0, window);
        return true;
    }
    //check for the respective window
    for (int i = window; i < str1.length(); i++) {
        //if the character that goes out of the 
        //window makes any difference in character count
        //then decrement count 
        if (hash_str2[str1[i - window]] != 0 && hash_str1[str1[i - window]] <= hash_str2[str1[i - window]] && hash_str1[str1[i - window]] > 0)
            count--;
        //removes the character from the window
        hash_str1[str1[i - window]]--;
        //stores the occurrence of new character
        hash_str1[str1[i]]++;
        if (hash_str2[str1[i]] != 0 && hash_str1[str1[i]] <= hash_str2[str1[i]])
            count++;
        //if all the characters of str1 and str2
        //matches then return true
        if (count == len2) {
            substring = str1.substr(i - window + 1, window);
            return true;
        }
    }
    //if there exists no any window of size window
    //which contains all the characters of str2
    //return false
    return false;
}
// Function to find smallest window containing 
// all characters of str2
string findSubString(string str1, string str2)
{
    //Initializing the search space
    int low = str2.length();
    int high = str1.length() + 1;
    //If the length of string2 is greater than string1 then
    //No window exists
    if (low > high) {
        cout << "No such window exists\n";
        return "";
    }
    int hash_str2[256] = {0};
    //Store the occurrence of the characters of string2
    for (int i = 0; i < str2.length(); i++)
        hash_str2[str2[i]]++;
    //Binary search
    while (low < high) {
        int mid = low + (high - low) / 2;
        //check if there exists a window of size mid
        //If true then update high with mid
        //else update low with mid+1
        if (check(str1, hash_str2, mid, str2.length()))
            high = mid;
        else
            low = mid + 1;
    }
    //If the substring is empty then no window exists
    if (substring == "") {
        cout << "No such window exists\n";
        return substring;
    }
    //return the substring
    return substring;
}
//Driver Code
int main()
{
    string str1 = "Cplusplus";
    string str2 = "Cpp";
    cout << "Smallest window is : " << findSubString(str1, str2);
    return 0;
}

Output:

Smallest window is : Cplusp 

Time complexity: O(m + log n)
Space complexity: O(n)