Last Updated: 4 Mar, 2021
Minimum Window Substring
Hard
Asked in companies
You are given two strings ‘A’ and ‘B’. Your task is to return a substring ‘S’ of ‘A’ such that the following conditions hold true :
• You can make ‘B’ from ‘S’ by removing some characters and rearranging some characters zero or more times.
• Length of ‘S’ must be as minimum as possible.
Note :
Testcases are generated such that a substring always exists and is unique.
Example :
A = ninjas, B = sin
All possible substrings with which 'B' can be created are
"ninjas", "injas".
Hence the substring with minimum length is "injas".
Input Format :
The first line contains two space-separated strings ‘A’ and ‘B’.
Output Format :
Print the substring with minimum length.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Approaches
The idea here is to generate all possible substrings of “A” and check if it contains all characters of “B” or not.
Algorithm :
- Declare a variable to store the minimum length of the required substring and another to store the starting index, say, ‘answer’ and ‘startignIndex’. Initialize it with the length of string ‘A’ + 1 and 0 respectively.
- Declare a map say ‘count’ and store the frequency of all characters of ‘B’ in it.
- Generate all substrings of ‘A’ by running two nested loops.
- Say the current substring of ‘A’ be ‘current’.
- Check if ‘current’ contains all characters of ‘B’. This can be done by counting frequency of all characters of ‘current’ in a map, say, ‘countCurrent’.
- If all characters in ‘count’ map have frequency less than equal to ‘countCurrent’ then update the answer with a minimum of the length of ‘current’ and value of ‘answer’ and also vale of ‘startingIndex’ respectively and then break.
- If ‘answer’ equals to length of string ‘A’ + 1 then return -1, else return ‘answer’.
The idea here is to use the sliding window technique. We will maintain two pointers left and right to get the minimum substring.
Algorithm :
- Declare a variable to store the minimum length of the required substring and another to store the starting index, say, ‘answer’ and ‘startignIndex’. Initialize it with the length of string ‘A’ + 1 and 0 respectively.
- Declare a map say ‘count’ and store frequency of all characters of ‘B’ in it.
- Declare a variable ‘need’ to keep track of the number of characters needed in the current substring and initialize it with length of string ‘B’.
- Declare two variables ‘left’ and ‘right’ to keep track of minimum size substring and initialize both of them with zero.
- Run a loop until right <= length of string ‘A’.
- If ‘need’ is greater than zero then :
- If right = length of string ‘A’ then break the loop.
- Decrement frequency of current character of string ‘A’ from map ‘count’.
- If the frequency of the current character in map ‘count’ is greater than or equal to zero then it means that this is required character in our substring. So decrement ‘need’ by 1.
- Increment ‘right’ by 1.
- Else :
- If right – left < answer then update ‘answer’ with right – left and 'startingIndex' with left.
- Increment frequency of current character in ‘count’ map by 1.
- If the frequency of the current character in map ‘count’ is greater than zero then it means that this is required character in our substring. So increment ‘need’ by 1.
- Increment left by 1.
- If ‘answer’ equals to length of string ‘A’ + 1 then return -1, else return a substring of a starting from ‘startingIndex’ and having a size of 'answer'.