Minimum Window Substring: Utilizing Two Pointers & Tracking Character Mappings With A Hashtable
VloĆŸit
- Äas pĆidĂĄn 24. 07. 2024
- Code & Problem Statement @ backtobackswe.com/platform/co...
Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
đč 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"
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech
++++++++++++++++++++++++++++++++++++++++++++++++++
This question is 13.7 in the fantastic book Elements of Programming Interviews - VÄda a technologie
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.
Please pin this.
sure
The link to the code is broken.
Boss no link for the code !
@@BackToBackSWE no code in description?
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!!!
thanks
Just love the way he explains.
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.
haha sure
No request, just major kudos. Your videos are by far the best leetcode explanations I've seen, please keep it up.
I'm trying to improve daily. Teaching is hard. It is one thing to know something. But I have to sit myself down and say...how do I communicate this?
The effectiveness of a teaching is inversely proportional to the number of people you lose at each great intellectual "leap" (as I always say) a concept requires.
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!
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.
yeah I will keep posting - and thanks haha, I've been at this for a while with little viewers
Wonderful video. You made what could be a confusing concept into a clear one. I feel immensely more powerful behind the keyboard now!
haha nice
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!
Interesting, thanks
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!
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.
Thank you!! Probably the only channel in the world where I won't touch the skip ad button or use ublock origin against.
aw, thanks. Well...this channel has a long way to go...the initial videos were a rough start.
Amazing work dude- I'm a fan of your code explanations! Keep em coming
aw
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!
The clearest explanation on CZcams. You deserve way more subs!
ye
I was solving some questions by myself and had doubts in some of them such as this one..and i came across your videos ..i must say you have put a lot of hard work in explanation and also in editing of your videos..hats off..SUBSCRIBED :)
thanks
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.
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().
I haven't replied to this for a bit, replying to close this out in my "unresponded to comments" feed.
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 .
thanks and ok
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.
hey -Ben
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?
Hope is the goal.
And...yeah I want to do an OOP/system design thing but for that I need more independent study. I read "Clean Code" and "Clean Architecture" by Robert C. Martin.
"Clean Architecture" is a fantastic, amazing, complete, book on good Object Oriented design and designing scalable OO systems.
And comments like this inspire me but make me sad too. I have hundreds of more quality videos in me...will the world ever see them? ... This project will take at least a year to develop into the minimum of what I want it to be.
That makes me sad.
A lot of hard work and lonely days ahead in front of a computer screen...but it's ok.
@@BackToBackSWE you did really really amazing work.
@@kellyxiao3060 haha thanks
@@BackToBackSWE you will be more searched on youtube in coming months if you continue to explain like this.Never ever loose hope.GOod Luck!
@@sahil_cse_guy2684 thx
I really like your approach of teaching, you start with brute force and then go on improving that.
Thanks!
sure
Thank you for all the work you put into creating these videos! You're awesome!
nah, u are
This is the most knowledge enhancing video i have seen for ds problems and it is to the point. keep the work good up.
Elated to hear that! Explore some awesome videos in our DSA course by subscribing on our website using "CZcams40" for a 40% discount - backtobackswe.com/pricing
It makes so much sense when you understood the technique, but man no way would I be able to come up with this technique in an interview
I have an interview of Monday and your videos are the besttttt
nice
I love all of your videos, thank you for making me understand everything better!
sure
You suddenly make the problem so easy to understand by abstracting and explaining the main thing. Thanks
sure
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 :)
Thanks for the nice words -Ben
You are the best teacher man! Thanks!
sure
absolutely brilliant! thanks for taking a chance on us!
I was just finding a teacher like you who teaches how to think, really you are a great teacher Sir......Lots of love and respect from India......
thanks haha, love from San Francisco
The Ω part is a little confused, but another part is very clear. Thanks, Ben. your video gives me a log help
Sure. And watch this: czcams.com/video/0oDAlMwTrLo/video.html
Very well explained!!! Thank you very much for taking the time and effort to walk through in this depth!
sure
great explanation. I don't know how to thank you. I really like the transition from a brute force solution to an optimal one.
sure
I really like the way you explained this problem. Very logical and easy to understand. Thank you!
you're the best bro seriously never stop please
One thing which will take you forward in this domain is the way to you approach problem and optimize it further. Keep it up. All the best.
nice
Expand the window until it satisfies, then contract the window. Nice explanation!
thanks. hey.
Thank you for the awesome explanation of both the algorithm and it's time and space complexity. I was struggling to understand the time and space complexity.
sure
so well explained, such a clear quick course!
very very thank you, sir, the way you approach is just like feeding a baby right from scratch it's just awesome this problem is right now in your assignment and I don't know how to solve it but by this, I can very easily do it
nice
Oh boy, oh boy. This is very good explanation. When you said this issue is consider "hard" I was suprised, since you made it so easy by breaking down this brute force and optimal solution. Cheers
haha thanks! Means a lot
I am a fan of your code explanations. I must say great way to explain something in very simple way.
thx
Doing leetcode for 2 days and I saw you 3 times! Subscribed!
hey
teaching is an art and you are gifted with that. thank you!
Thanks! try out my 5 day free mini course for some good content backtobackswe.com/
Very well explained! Saved my time and it is very helpful! Thank you!
nice
There's a LC easy question (#438) like this that my friend and I were struggling with. Brute force solution is easy to come up with, but the optimal solution requires a little bit more practice. This video explained it perfectly. I've been watching your videos daily! Ordered EPI because of you and it came in the mail this morning.
sweet, that's a good book. Tell me when you get into Google đđ
@@BackToBackSWE First phone interview in a couple weeks đ. I'll let you know if I make it to their on-sites!
Thank you. The example driven explanation really brings clarity to my understanding.
nice
Excellent explanation!!! Really like to watch and learn from your tutorials.
sure
Your videos are so helpful and clear.
It was a very well made with emphasis on important words and points. Loved the video and you earned a sub.
welcome aboard đą
This is so helpful. Thanks a lot.
One of the most readable codes - 100 times better than those on leetcode discuss - Very easy to understand for anyone - Actually had figured out the approach before watching your video - But had problems implementing it myself - Thanks Ben !
Nice, thx
@@BackToBackSWE Just a small suggestion in your optimal code - We can maintain the frequency mapping only for required characters (those present in String t) in 'windowCharacterMapping' hashmap - As we do not care for characters which are not present in String t
Thanks for the clear explanation. You make the logic so easy to understand.
sure
I was confused while solving leetcode Sliding window questions. Leetcode discussion section didn't help. Watched this video and now I am able to solve most of sliding window medium level questions in 15-20mins. Thanks for the video
haha great
Wow, This is the best explanation, Thank you for making our lives easier.
Thank you very much, this really helped a lot.
You explain like a real man... Amazing
lol thx
Awesome explanation!
You are a brilliant teacher!!!! You really built the concepts.
thanks
Awesome explanation! I really appreciate your efforts. Thanks!
ye
your teaching skill ismawesome man !!! love it
thanks
OMG such neat intuitive explanation! Thanks for your efforts!
Also, you have a lot of resemblance with one of my cousins and we are Indian! :)
Ay, Indian fam
Beautifully explained!
thanks
Thanks! In the code while mentioning about time complexity instead of mentioning leetcode runtime, put it in terms of big o notation, that would be more helpful.
good suggestion
As always thank you !
Awesome explanation. Thank you so much for making such good videos. Helping us a lot.
sure, may the internet flourish
Well explained!! Thanks!! I would like to know how the characters are search within the window using the hash table in O(1) time.
I don't remember this problem well nor the solution enough to answer
I've discovered the channel, great explanation, thanks!!
EXCELLENT!!!!!! Thank you, you've made my day.
no u
Thank you for the good explanation.
Very Helpful,
Fantastic Explanation
dude you really are a legend
Great explanation, thanks for the video. Helped me a lot in understanding the problem in preparation for an upcoming Facebook interview
great.
best ! love how you cut videos
thanks
Thank you! I was struggling with this.
glad it helped
I wish I found this channel earlier, u r so good
welcome & no ur gud
I can only say ,"YOU ARE THE BEST"
no, I'm decent
Concise and precise explanation.
Excellent and clear explanation. In a sea of heavy accents and confusing explanations, you video is like water in the desert. Thanks!
thanks hahaha đïžđ§
Beautifully explained. Thanks!
Thank You, Glad you liked it.
Do check out backtobackswe.com/platform/content
and please recommend us to your family and friends :)
Your explanations are the best in the world!
thanks
Awesome video with great explanation. Thanks a lot for such amazing and easily understandable video
THANK YOU SO MUCH
Super clear man, thanks!
sure
Trust me, a very clear explanation. I will definitely donate when I pass my interview. lol
Lovely intuitive explanation!
Thank you!
it's my 1st video on this channel............... and guess what? I love it by your approach to the solution .!!
nice
Amazing explanation. You're awesome at this.
thanks
Just love the way you explain things. Your videos are the best. Good job đ đ
thanks! hey
@@BackToBackSWE Hi, I am stuck on this question (www.lintcode.com/problem/word-pattern-ii/description). Can you please create a video for the same.
Really nicely explained, thanks man!
sure
21:30 I understand that it takes O(t) to build the hash table, but since there are total 26 characters, wouldnât it take O(1) to store the hash table? Thanks.
you earned a sub man
welcome
You got it, keep on doing...
Somebody give this guy a medal!
ok
Very good explanation. Thank you Sir for this quality video.
One of best explanation of complexity analysis .. keep going ... many likes
sure
thank you, sir, for this beautiful explanation. Made me subscribe and happy to watch your more videos and get good knowledge .
hahaha nice, thanks
I think I am dumb af, cOZ I hAve To KeEp rePlaYing ThE vIdEO
EDIT: finally got it ! you genius teacher man !
lol great
Huge thanks! You're awesome!
sure