Leetcode Solution #8

1. Minimum Window Substring

Even after less views and no comments I am back coz can't let the culture and streak die hahahaha.....

Anyways today's question is leetcode hard and took some time to me too solve it but yea did it somehow.

The Problem

Let's try to understand it's description first,

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique.

Now I will call this description a very poor explanation of the question, basically the question is saying that we have given two strings s and t and length of these strings are m and n respectively, we are asked to return a minimum window substring of s such that every character present in t is included in the window we are returning.

See these examples to make sense of what I said,

Well question is kind of messed up but not that bad, have confidence you can do it. Let's move to approach.

The Approach

We will do the same thing which we do when we have two strings to compare, i.e.

1. Store occurrence of characters of string t.
2. Count occurrence of characters of string s.
3. If all characters matched, minimise the window.
4. Update window size.
5. Return substring.

Looks pretty easy isn't it but code looks a little bit scary. But I have tried my best to make it easy in steps.

The Solution

So, steps to achieve this crazy code are,

1. Check if length of t is longer than s if it is return empty string.

2. Declare two vectors of size 256 initialised to 0.

3. Populate hashT with counts of character in t using for loop.

4. Declare variable start as starting index of current window in s, start_index keeps track of the best starting index for minimum window found, min_len initialises to max possible integer value, count to count how many characters from t we have matched in current window.

5. Loop through each character in s.

6. Increment the count for character s[j] in hashS.

7. If s[j] is a character in t and the count in hashS for that character does not exceeds that in hashT, we found a match and we increment count.

8. Check if all characters are matched.

9. Inner loop shrinks the window from left until we can no longer maintain all characters in t.

10. Calculate current window length.

11. If this length is less, update the length and set start_index to current start.

12. Return result.

Damn such a complex question isn't it that's why only one for today hehe, if you will attempt this you will need time to digest this and don't quit.

And please please if you are liking this atleast react to it comment on it criticise it if you are not liking come on don't be like this.

Connect to me on Linkedin and Github.

Come on man I deserve some fame.

Thank you if you are following this blog till here, have some confidence you can do it.

KEEP CODING!!!