{"id":1338,"date":"2020-06-10T19:09:36","date_gmt":"2020-06-10T19:09:36","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1338"},"modified":"2022-11-18T12:16:19","modified_gmt":"2022-11-18T12:16:19","slug":"minimum-window-substring","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/minimum-window-substring\/","title":{"rendered":"Minimum Window Substring"},"content":{"rendered":"

\"\"<\/p>\n

\n

Find the minimum size of the substring of string S<\/code> which contains all the character from a given string T<\/code>. Print the substring with minimum length.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Test Case<\/h3>\n
Input:\n1\nprepbytes\npyte\nccbabcab\nbbab\n\nOutput:\npbyte\nbabcab\n\nExplanation:\nCase 1: All characters in string 'pyte' are present in 'pbyte' and this is the smallest substring.\nCase 2: All characters in string 'bbab' are present in strings 'babcab' and this is the smallest substring containing all characters.<\/code><\/pre>\n
Bruteforce Approach to Solve the Minimum Window Substring Problem –<\/h2>\n
\n
1) We can generate all substrings of string S<\/code>.
\n2) For each substring we check if it contains all character from the string T<\/code>.
\n3) We print the string with minimum length.
\n4) You can see this approach is not efficient and takes O(T\\times{N^{2}}<\/code>) time as it takes O(N^{2}<\/code>) time for calculating all substrings and takes O(T<\/code>) time for checking if all characters from T<\/code> exists or not in the substring.
\n5) Do you have any other approach which is efficient than this approach? Try that out, if that one goes beyond the time limit, proceed to the following efficient approach.<\/p>\n<\/blockquote>\n
In the above approach, we found all substring containing all characters from our pattern string, we can also observe that all discarded substring contain or minimum window substring, and the largest such substring starts from 0. Hence we can find a substring from the start of the string containing all characters from the pattern, and then discard characters from beginning one by one, until we reach a condition that violates our requirements. We discuss this approach our efficient approach<\/code><\/pre>\n
Efficient Approach to Solve the Minimum Window Substring Problem:<\/h2>\n
\n
1) First check if the length of string S<\/code> is less than the length of the given string T<\/code>, if yes print Not Found<\/code>.
\n2) If no, then store the occurrences of characters from string T<\/code> in a hash table.
\n3) Start matching the characters of string T<\/code> with the characters of string i.e. increment count if a character matches.
\n4) Check if the count is equal to the length of string T<\/code>, if yes we have found a window containing all characters from the string T<\/code>.
\n5) If such a window is found, try to minimize it by removing extra characters from the beginning of the current window.
\n6) Update the minimum length on each character removal.
\n7) Print the window with minimum length when no character can be removed.<\/p>\n<\/blockquote>\n
Example<\/h3>\n
\n
    \n
  • Let us take an example and understand above approach, let string S<\/code> be ‘qabaaab<\/code>‘ and pattern P<\/code> be ‘baaab<\/code>‘.<\/li>\n
  • We maintain a hash table hash_str<\/code> to store characters from string. We also maintain a hash table hash_pat<\/code> to store characters from pattern string.<\/li>\n
  • We find all appearances of characters in hash_pat<\/code>, so final hash_pat<\/code> for pattern is [3,2]<\/code> where index 0<\/code> corresponds for character a<\/code> and index 1<\/code> corresponds for character b<\/code>.<\/li>\n
  • We now find the largest window containing all character from pattern string, this can be found by starting window from 0<\/code> and increasing end of window one by one until whole window contains all chracters from pattern string.
    \nHash table for string is initialised with 0, so default hash table is [0,0,0]<\/code> where index 0<\/code> corresponds to 'a'<\/code>, index 1<\/code> corresponds to 'b'<\/code> and index 2<\/code> corresponds to 'q'<\/code>.<\/li>\n<\/ul>\n<\/blockquote>\n
    Finding Window :<\/em><\/strong><\/p>\n
    \n
    We also maintain a counter count<\/code>, which when equal to length of pattern, we exit because that is last point of window.<\/p>\n<\/blockquote>\n
    For end = 0:<\/em><\/strong><\/p>\n
    \n
    Current character is 'q'<\/code>, hence hash_str<\/code> becomes [0,0,1]<\/code>, ‘q’ does not appear in pattern, so we don’t increase count<\/code>.<\/p>\n<\/blockquote>\n
    For end = 1:<\/em><\/strong><\/p>\n
    \n
    Current character is 'a'<\/code>, hence hash_str<\/code> becomes [1,0,1]<\/code>, hash_str value is less than hash_pat value of ‘a’, so we increase counter by 1, so count=1<\/code>.<\/p>\n<\/blockquote>\n
    For end = 2:<\/em><\/strong><\/p>\n
    \n
    Current character is 'b'<\/code>, hence hash_str<\/code> becomes [1,1,1]<\/code>, hash_str value is less than hash_pat value of ‘a’, so we increase counter by 1, so count=2<\/code>.<\/p>\n<\/blockquote>\n
    For end = 3:<\/em><\/strong><\/p>\n
    \n
    Current character is 'a'<\/code>, hence hash_str<\/code> becomes [2,1,1]<\/code>, hash_str value is less than hash_pat value of ‘a’, so we increase counter by 1, so count=3<\/code>.<\/p>\n<\/blockquote>\n
    For end = 4:<\/em><\/strong><\/p>\n
    \n
    Current character is 'a'<\/code>, hence hash_str<\/code> becomes [3,1,1]<\/code>, hash_str value is equal to hash_pat value of ‘a’, so we increase counter by 1, so count=4<\/code>.<\/p>\n<\/blockquote>\n
    For end = 5:<\/em><\/strong><\/p>\n
    \n
    Current character is 'a'<\/code>, hence hash_str<\/code> becomes [4,1,1]<\/code>, hash_str value is greater than hash_pat value of ‘a’, so we dont increase counter, so count=4<\/code>.<\/p>\n<\/blockquote>\n
    For end = 6:<\/em><\/strong><\/p>\n
    \n
    Current character is 'b'<\/code>, hence hash_str<\/code> becomes [4,2,1]<\/code>, hash_str value is less than hash_pat value of ‘a’, so we increase counter by 1, so count=5<\/code>.<\/p>\n<\/blockquote>\n
    Hence count is now equal to length of pattern, so we have found the window of maximum length, now we need to short this window for minimum size of window.<\/p>\n
    <\/blockquote>\n
    Minimizing The Window :<\/em><\/strong><\/p>\n
    \n
    Here, we move start pointer of window to minimize the size, we decrease the count of hash_str value of current character if hash_str value is greater than hash_pat value of current character. If hash_str value becomes becomes less to hash_pat value of current character, we stop iterating, current window is the minimum window.<\/p>\n<\/blockquote>\n
    For start = 0:<\/em><\/strong><\/p>\n
    \n
    Current character is 'q'<\/code>, hence hash_str<\/code> becomes [4,2,0]<\/code>, hash_str value is not in pattern so we move further.<\/p>\n<\/blockquote>\n
    For start = 1:<\/em><\/strong><\/p>\n
    \n
    Current character is 'a'<\/code>, hence hash_str<\/code> becomes [3,2,0]<\/code>, hash_str value of ‘a’ is greater than hash_pat value, so we move window further.<\/p>\n<\/blockquote>\n
    For start = 2:<\/em><\/strong><\/p>\n
    \n
    Current character is 'b'<\/code>, hence hash_str<\/code> becomes [2,2,0]<\/code>, hash_str value of ‘a’ is equal to hash_pat value, so we have minimized the window.<\/p>\n<\/blockquote>\n
    We print the final window starting from start to end pointer. Hence we print 'baaab'<\/code>.<\/p>\n
    Program of the Solution of Minimum Window Substring Problem<\/h2>\n
    \t\t\t\t\t\t