Minimum Window Substring: Utilizing Two Pointers & Tracking Character Mappings With A Hashtable

📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions

Question: Given a string S and a string T, find the minimum window in S which will contain all the characters in T (matching or exceeding in frequency) in complexity O(n).

Anytime we have time reduced to linear time and we know that much must be done, that is indicative of using some sort of auxiliary structure to keep track of information for us so time can stay low in complexity.

Complexities

s = length of search string
t = length of "pattern" or "character" string

Time: O( s + t )
At worst we will touch each element twice, once by the left pointer and once by the right pointer.

Ex:
s = "aaaaat"
t = "t"

We will spend t time to build the character requirements hashtable.

Space: O( s + t )

At worst the window hashtable will have a mapping for every character in s.

At worst t will have all unique characters.

s = "abcdef"
t = "abcdef"

++++++++++++++++++++++++++++++++++++++++++++++++++

++++++++++++++++++++++++++++++++++++++++++++++++++

This question is 13.7 in the fantastic book Elements of Programming Interviews

[BackToBackSWE]

Table of Contents:

The Problem Introduction 0:00 - 1:31
Walking Through The Brute Force 1:31 - 4:19
Analyzing The Brute Force Solution 4:19 - 6:58
Lower Bounding The Brute Force 6:58 - 10:25
Let's Think Harder: Reapproaching Things 10:25 - 13:03
First Satisfying Window Found 13:03 - 13:51
We Now Make A Key Choice 13:51 - 17:43
Observing The Work The More Optimal Solution Does 17:43 - 19:25
Time Complexity 19:25 - 20:35
Space Complexity 20:35 - 21:36
Wrap Up 21:36 - 22:14

The code for both Brute Force and Optimal solutions are in the link in the description. Fully commented for teaching purposes.

[aholagunju]

Why am I just discovering this channel? This is the best explanation I have seen so far. Makes it look simple as "abc".

Thank you Ben.

[SameerSrinivas]

Thanks a lot for choosing intuition based approach. This is the most important skill in problem solving. Thanks for your time and energy spent making these videos and for writing beautiful code. Was able to understand with no confusion. Those are very intuitive variable names! Keep rocking!!!

[doruwyl]

I've watched a lot of video explanations to different coding problems.
But I can say for sure that your way of explaining things is by far the best I've seen so far.
I consider that you really try your best to make the audience to understand the solution to the problem rather than just showing a problem.
Well done!
I hope you will keep up posting new videos!
Definetively this channel should have a lot more subscribers.

[neerumittal]

This is the most knowledge enhancing video i have seen for ds problems and it is to the point. keep the work good up.

[Egrodo]

No request, just major kudos. Your videos are by far the best leetcode explanations I've seen, please keep it up.

[jral]

It took me so long to finally find a resource that makes sense. Your video and website is easy to understand and pure gold. Glad I found your channel from this problem, thanks!

[saurabhverma]

I watched this video 5 years back, to figure out how to code this problem up.
I am again watching this video after 5 years, but to validate my the way of thinking today.
Damn, I have grown, from only wanting to know how to blindly code things to wanting to practice and polish critical thinking!

Man, what a channel this was.

[xsnowcappedx]

Man I just graduated and started job hunting. These videos have finally made everything I've studied start to come together ( I really couldn't understand a lot ). EVERY other video/explanation has been so confusing for me. You're genuinely giving me hope. Keep this up I really appreciate it. Do you plan to cover any kind of OOP design or system design/scalability questions?

[dankokozar]

Brilliant. I believe it's very hard to edit the video in a stop-motion fashion and you're making that effort. That makes your videos interesting from start to end. I also like big and clear letters (visible on tablet). Kudos!

[ponderatulify]

You are a WONDERFUL educator. That's how my mind works. I can't go full abstract from the get-go. I start simple from a concrete case, specific case, then I can generalize. Always thought this was wrong, because I wasn't able to REMEMBER solutions... . Thank you man.

[jordanmoore]

Wonderful video. You made what could be a confusing concept into a clear one. I feel immensely more powerful behind the keyboard now!

[jlpeng]

thank you man! your explain is wonderful!!! a lot of people tried to explain their code, but you are the first one explaining how the idea (the way we should think) to solve it without coding part. i now understand it!

[namratam]

Hi Ben, I had been searching for these all problems to be explained around "Why" and "How", you have made me stop my search and I struggle to believe that someone could teach better than my expectations. I am from India and love the way you teach, amazing man.

[aasthamehtatech]

I'll mark today's date by this comment, I really did watch a few ur videos earlier, but today is when I realised the beauty of it! All this time, I jumped to problem solving directly, hoping to learn algorithm or even come up with 'em when I solve problems, now I do realise that first we need to understand the concept that deep, know y we r doing it & only then we'll able to come up with beautiful efficient soln. Also, I did like ur way of transitioning from intuitive brute force to an efficient one, that makes the content even more relatable. Thanks @BackToBackSWE :)

[James-yzcc]

The clearest explanation on Youtube. You deserve way more subs!

[kratigupta]

You are doing a fantastic job I must say, and I just now saw your platform where u have put code, solution, video all at one place, and it is God level.

[xiuwenzhong]

thanks a lot for hint of this problem.
Using one HashMap to store all the target character and the times they need to show. Once the value change to 0, match length + 1, (when fast point move), once the value change from 0 to 1, match length - 1, the way to check current substring is contain target string, we can use matchLength == map.size().

[RahulVerma-fzjf]

Really good work man. The best part is you, explaining the thinking process of how to go about optimizing brute to a better solution. Keep up the good work .

[kannappansuresh]

crystal clear explanation, thanks man. got stuck with problem for two days, I wanted a in-depth explanation of the algorithm and you provided it!