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.
- First check if the length of string is less than the length of the given pattern, if yes then “no such window can exist“.
- Apply binary search . l= sizeof(string2) and r = sizeof(string1)+1.
- 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.
- Store the occurrence of characters of the given pattern in a hash_str2[].
- Start matching the characters of string2 with the characters of string1 i.e. increment count if a character matches.
- 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)