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

[@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.

[@akhileshsingla3212]

Please pin this.

[@BackToBackSWE]

sure

[@akhilk5121]

The link to the code is broken.

[@mmfawzy4850]

Boss no link for the code !

[@023ankit]

@@BackToBackSWE no code in description?

[@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!!!

[@BackToBackSWE]

thanks

[@vivekgr3001]

Just love the way he explains.

[@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.

[@BackToBackSWE]

haha sure

[@enigma2886]

I think I am dumb af, cOZ I hAve To KeEp rePlaYing ThE vIdEO EDIT: finally got it ! you genius teacher man !

[@BackToBackSWE]

lol great

[@Chiving]

No way someone can come with this solution on 45 minutes

[@BackToBackSWE]

Yeah

[@kanishkkumar4746]

I came to this idea just after seeing the solution and even when am not good !

[@th3tagang]

you are not being interviewed on your experience, but on your ability to memorize these problems. I know people will claim, oh, there are concepts to understand, but the reality is your ability to develop object oriented systems cannot be determined with hundreds of algorithms that have their own niche.... Unfortunately, we are perpetuating this by studying for interviews...

[@kanishkkumar4746]

@@th3tagang you are wrong buddy there are people who can solve problems without doing leetcoding (i.e. memorizing problems ) , an extreme example can be Gennady korotkevich !

[@zlmsailor]

@@kanishkkumar4746 You could not possibly find tens of thousands of them to meet the demand of FAANG.

[@Egrodo1]

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

[@BackToBackSWE]

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.

[@RagazzoKZ]

You are the best teacher man! Thanks!

[@BackToBackSWE]

sure

[@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!

[@BackToBackSWE]

Interesting, thanks

[@suhasnayak4704]

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.

[@BackToBackSWE]

good suggestion

[@jordanmoore7298]

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

[@BackToBackSWE]

haha nice

[@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?

[@BackToBackSWE]

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.

[@kellyxiao3060]

@@BackToBackSWE you did really really amazing work.

[@BackToBackSWE]

@@kellyxiao3060 haha thanks

[@sahil_cse_guy2684]

@@BackToBackSWE you will be more searched on youtube in coming months if you continue to explain like this.Never ever loose hope.GOod Luck!

[@BackToBackSWE]

@@sahil_cse_guy2684 thx

[@muneerhasan]

Deserve one like from India

[@BackToBackSWE]

welcome

[@kaushtubrawat8223]

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 :)

[@BackToBackSWE]

thanks

[@edwardnewgate2198]

Amazing work dude- I'm a fan of your code explanations! Keep em coming

[@BackToBackSWE]

aw

[@fancytseng]

May I ask where are the codes in the description? I am willing to pay as well but just dont know where it is. It seems to have too many links and I could not find it. Thanks

[@BackToBackSWE]

The repository is deprecated - we only maintain backtobackswe.com now.

[@neerumittal9028]

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

[@BackToBackSWE]

Elated to hear that! Explore some awesome videos in our DSA course by subscribing on our website using "KZbin40" for a 40% discount - backtobackswe.com/pricing

[@derreck3424]

Code link is dead (404 error)

[@BackToBackSWE]

ik, dont have time to fix it

[@brandonhui1298]

was asked this by a big n, its a good problem

[@BackToBackSWE]

hey

[@brandonhui1298]

@@BackToBackSWE is for horses

[@BackToBackSWE]

@@brandonhui1298 yeah

[@kirancoding1576]

I can only say ,"YOU ARE THE BEST"

[@BackToBackSWE]

no, I'm decent

[@Mohith7548]

Space complexity can be O(1) if we use array of len 26, rather than Hashtable.

[@BackToBackSWE]

ok

[@jenny3416]

there's uppercase and lowercase, and they don't treat them as the same input: s="a", t="A" output: ""

[@VijaySharma-hw4kv]

@@jenny3416 still O(1) space. if we consider all chars with 256 length

[@liingpangryantee7203]

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

[@sophiehall38]

Expand the window until it satisfies, then contract the window. Nice explanation!

[@BackToBackSWE]

thanks. hey.

[@James-yz4cc]

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

[@BackToBackSWE]

ye

[@maruthiteja2586]

Why u stopped making video's.Do more it will be more helpful for us.

[@BackToBackSWE]

To build out backtobackswe.com

[@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.

[@BackToBackSWE]

yeah I will keep posting - and thanks haha, I've been at this for a while with little viewers

[@xiuwenzhong7375]

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().

[@BackToBackSWE]

I haven't replied to this for a bit, replying to close this out in my "unresponded to comments" feed.

[@shashankkumarshankar3655]

You explain in such low level details with focus on the "why" than just the "how" makes you a 1000 times better than Tushar Roy's videos :P. Great work! I am pretty sure you would be great to work with in real software engineering.

[@BackToBackSWE]

thanks lol, tell that to all the companies that have rejected me 😳😳

[@southern-sunshine]

@@BackToBackSWE completely agree with shashank. BTW it's loss of companies which rejected you 😀

[@BackToBackSWE]

@@southern-sunshine ye

[@shashankkumarshankar3655]

Back To Back SWE haha. Yeah it happens. Interviews are okay with false negatives than false positives. Unfortunately that's the nature of it and nothing can be done.

[@BackToBackSWE]

@@shashankkumarshankar3655 ye

[@abhishekbhaware6719]

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

[@BackToBackSWE]

nice

[@danielol_99]

I had this exact same question in my Facebook interview, in case anybody wonders :)

[@AyushiSharmaDSA]

thank u so much for this video

[@BackToBackSWE]

sure

[@ramadaskamat6418]

I wish I found this channel earlier, u r so good

[@BackToBackSWE]

welcome & no ur gud

[@gurpartapsingh1693]

Hey, brilliant job man. But I couldn't find the link to the code. Can you help me through it?

[@BackToBackSWE]

The repository is deprecated, we only maintain backtobackswe.com now.

[@atibhiagrawal6460]

I have an interview of Monday and your videos are the besttttt

[@BackToBackSWE]

nice

[@The8merp]

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.

[@BackToBackSWE]

sure

[@chchhite119]

Hi,cloud you supply extra code implementation.Thanks!

[@BackToBackSWE]

We only maintain code on backtobackswe.com now

[@TheRahul599]

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......

[@BackToBackSWE]

thanks haha, love from San Francisco

[@jral1127]

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!

[@harishgovindan]

Well explained!! Thanks!! I would like to know how the characters are search within the window using the hash table in O(1) time.

[@BackToBackSWE]

I don't remember this problem well nor the solution enough to answer

[@vanshmittal767]

your teaching skill ismawesome man !!! love it

[@BackToBackSWE]

thanks

[@fridagutierrezmireles1193]

I love all of your videos, thank you for making me understand everything better!

[@BackToBackSWE]

sure

[@anikpait5556]

Amazing explanation! I didnt get the part of why S was there in Space Complexity?

[@BackToBackSWE]

I don't remember this video too much

[@saikatchakraborty6291]

awesome brother subscribing for more content from your channel

[@BackToBackSWE]

sounds good

[@lokeshnamala4218]

Where can I find the code for this problem ? Please help me.

[@BackToBackSWE]

The repository is deprecated - we only maintain backtobackswe.com now.

[@Yunnn_life]

Doing leetcode for 2 days and I saw you 3 times! Subscribed!

[@BackToBackSWE]

hey

[@jishulayek8252]

Excellent explanation!!! Really like to watch and learn from your tutorials.

[@BackToBackSWE]

sure

[@AI_For_Scientists]

teaching is an art and you are gifted with that. thank you!

[@BackToBackSWE]

Thanks! try out my 5 day free mini course for some good content backtobackswe.com/

[@shersanginov1792]

i think two pointer approach is called Sliding Window pattern

[@BackToBackSWE]

yeah

[@techsavvy1457]

Again, the code is the description and is commented out.

[@BackToBackSWE]

hey

[@willturner3440]

Congratulations sir you got a new subscriber 🥳🥳

[@BackToBackSWE]

welcome aboard

[@biswamohandwari6460]

You explain like a real man... Amazing

[@BackToBackSWE]

lol thx

[@pranjalchoubey5929]

Beautifully explained!

[@BackToBackSWE]

thanks

[@CODINC]

I like your explanation but your code can be simplified though because there are a lot of comments and your naming of variables are too long. It is easy to get lost in that code.

[@BackToBackSWE]

yeah, you are right

[@darod6098]

Hi! Excellent video. I don't understand something in the code (but it works!). After initializing left and right you wrote "totalCharFrequenciesToMatch is the total characters we need to match frequencity for in the window. If i have 1 'a' in my window and I need 2 'a' then the char frequencies don't match". But then, you coded: int totalCharFrequenciesToMatch = requiredCharacters.size() requiredCharacters is a hashmap, so the size of it will be the number of entries (key,value) that it has, in other words the number of different characters that it contains but not the total of occurrencies that we need, so I don't get why it works. Can you help me to understand that? :)

[@BackToBackSWE]

Yes. requiredCharacters is a hashmap. "totalCharFrequenciesToMatch" is the total number of character frequencies that we need to match up to. Not the total characters...TOTAL...across all mappings...to match. Imagine this: requiredCharacters = { 'a' => 2 'b' => 2 'w' =>3 } totalCharFrequenciesToMatch will be 3. We need to match ALL 3 mappings AT THE LEAST. At all times we see whether we have satisfied a mapping or broken the satisfaction of a mapping by: 1.) Snagging the character on the right of the window 2.) Seeing if it matters for the requirement 3.) Seeing if we hit the target and have 1 more "charFrequenciesInWindowThatMatch" The code is really beefy and not perfect...I'm sorry about that.

[@darod6098]

@@BackToBackSWE I understand it now :) Thanks for your time, it was a really good explanation

[@fibber7062]

Thank you for all the work you put into creating these videos! You're awesome!

[@BackToBackSWE]

nah, u are

[@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 :)

[@BackToBackSWE]

Thanks for the nice words -Ben

[@anonymoussloth6687]

At 14:54, when the string didn't satisfy, why couldn't we move L back to where it was and R to next position? Then the new substring would be "zjsk" which satisfies. Why do we not explore this option?

[@yomamasofat413]

all this talk of satisfying, lengthening and shortening really sounds like my ex

[@kedikebba6441]

No, you did not make any mistakes. Not even one.

[@BackToBackSWE]

ok lol

[@surajch2678]

Can you please fix the github link in your description ?

[@BackToBackSWE]

yes, but cant rn

[@surajchada8235]

Found it from your repo: github.com/bephrem1/backtobackswe/blob/master/Hashtables/MinimumWindowSubstring/Optimal.java

[@satyadeeproat2012]

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

[@BackToBackSWE]

haha great

[@rayaqin]

not a fan of the "minimum complexity" part being injected in the middle, maybe at the end as an extra would have resulted in better pacing overall

[@pallav29]

Very nice explanation. Though the video is a bit lengthy compared to other videos online, but it makes concept crystal clear .

[@BackToBackSWE]

ye

[@darthvader_]

Most Important line: First I worry about satisfying my constraints and then I look at how do I minimize them?

[@rohitpal7739]

best ! love how you cut videos

[@BackToBackSWE]

thanks

[@atharvavats2140]

The github link is not working. I wanted to see the code, could someone help me ?

[@BackToBackSWE]

i just moved things around

[@atharvavats2140]

Back To Back SWE Oh well, how do i access to code now ? Can you maybe post the new link to the code ? Also hats off to you, i got a call for google onsite studying your videos.

[@atharvavats2140]

github.com/bephrem1/backtobackswe/tree/master/Hashtables/MinimumWindowSubstring I was able to find this code from one of the other videos. Just in case if anyone still wants the link

[@CamiloDS]

I love your videos and they help a lot but the analysis is not correct. The lower bound is big-omega(n) and the upper bound is O(n^2).

[@shubhamkant_]

make 1 video for dry run of the code too.

[@BackToBackSWE]

ok

[@Liokki]

Great explanation, thanks for the video. Helped me a lot in understanding the problem in preparation for an upcoming Facebook interview

[@BackToBackSWE]

great.

[@kanishkkumar4746]

U r analysing the time complexity with a single char to search, but we if we have strings of length n and m , wont it be n*m , because we need to check whether the range have all the elementa of another string in it or not?

[@tanujdeepsingh2572]

Hey, loved the video, but can anyone please explain how are we checking if the window satisfies the condition in O(1) .

[@BackToBackSWE]

We keep track of unsatisfied characters (characters remaining to be satisfied). If it is >0 then the window is not satisfactory

[@James-yz4cc]

Can you do a video on "Longest Substring with At Least K Repeating Characters" (Leetcode 395)? I cracked Minimum window substring eventually but still stuggled on this one.

[@BackToBackSWE]

yes

[@AKHILPOKLE]

the example string looks like "adobe code banc" ,hidden message ? Thanks for explaining in a crystal clear format. cheers !

[@BackToBackSWE]

sure

[@akshatojha7791]

unable to find the link for code.

[@BackToBackSWE]

the repo is deprecated

[@himanshu715]

Nice Explanation. Keep Going

[@BackToBackSWE]

ok.

[@dwstyagi]

Please start trie data structures and some of its problem..BTW I've watched all of your videos and they are the best.

[@BackToBackSWE]

nice! and I cover tries in the class I run but I may do a problem on the channel if I get the time

[@Andy-ib3tf]

Thanks for the video. I have one question. How come the lower bound is O(n^2) but the time complexity is O( s + t ) which is smaller than O(n^2)?

[@BackToBackSWE]

Lower bounds are commonly notated with Big Ω so you mean Ω(n^2), and I don't remember this problem and its solutions well enough to give insight to the 2nd part.

[@AMITKUMAR-te9bn]

How the complexity be linear , since at each iteration we are checking whether the conditions (i.e all the req elements are present or not) .

[@BackToBackSWE]

I dont remember the code

[@shashikantdivekar7839]

Very good explanation. Thank you Sir for this quality video.

[@namratam1522]

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.

[@BackToBackSWE]

hey -Ben

[@HumalDiscover]

You suddenly make the problem so easy to understand by abstracting and explaining the main thing. Thanks

[@BackToBackSWE]

sure

[@RahulVerma-fz2jf]

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 .

[@BackToBackSWE]

thanks and ok

[@Harshseth3]

Isn't this more of a minimum window subsequence than a substring?

[@yuktikhantwal2342]

man you are great at explaining.... i just wish i could come up to such solutions on my own instead of taking help :(

[@BackToBackSWE]

I didn't solve this - I learned the solution and teach it here. I'm of average intelligence. You are fine.

[@nikhil.pandey]

it's my 1st video on this channel............... and guess what? I love it by your approach to the solution .!!

[@BackToBackSWE]

nice

[@yfzhai1732]

Can you do a sum of two integers without using operators "+" and "-" pleaszzzzz, it is killing me!

[@BackToBackSWE]

hahahahaha, every comment section is turning into requests 😂😂😂 ... maybe? Yeah, I'll do bit shifting things down the road. Trust me...actually don't do that, minus the trust part.

[@yfzhai1732]

@@BackToBackSWE No worries, I like all the videos you posted. They are all valuable

[@BackToBackSWE]

@@yfzhai1732 FINEEEEE. Here: github.com/bephrem1/backtobackswe/blob/master/Arrays%2C%20Primitives%2C%20Strings/additionWithOnlyBitshifting.java Just wrote that up, I'll do a video on it soon.

[@yfzhai1732]

@@BackToBackSWE You are the BEST!!!!

[@BackToBackSWE]

@@yfzhai1732 I know, if anything is confusing just ask...I'll have it out next week. I'll be away the next 3 days.

[@asittripathy1778]

I am a fan of your code explanations. I must say great way to explain something in very simple way.

[@BackToBackSWE]

thx

[@RDharini-yg1nm]

Very Helpful, Fantastic Explanation

[@sciphilo754]

Lovely intuitive explanation!

[@BackToBackSWE]

Thank you!

[@MAK28031991]

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.

[@BackToBackSWE]

nice

[@ibrahimt09]

Very well explained!!! Thank you very much for taking the time and effort to walk through in this depth!

[@BackToBackSWE]

sure

[@tushargupta5805]

where is the link to the code ??

[@BackToBackSWE]

The repository is deprecated - we only maintain backtobackswe.com now

[@cbverma2k]

One of best explanation of complexity analysis .. keep going ... many likes

[@BackToBackSWE]

sure

[@vasachisenjubean5944]

Alright u are best. Thats it.

[@BackToBackSWE]

thanks

[@tianxiaowang3771]

The Ω part is a little confused, but another part is very clear. Thanks, Ben. your video gives me a log help

[@BackToBackSWE]

Sure. And watch this: kzbin.info/www/bejne/ZqCncp-DrLmlgtE

[@vekatasaiamulyapamidimukka7085]

Awesome explanation. Thank you so much for making such good videos. Helping us a lot.

[@BackToBackSWE]

sure, may the internet flourish

[@danielcox4001]

My understanding is satisfied

[@BackToBackSWE]

ok

[@girishgarg2816]

legend says that he is still hearting the comments PS : He will heart this comment too

[@sreerampanigrahi]

It was a very well made with emphasis on important words and points. Loved the video and you earned a sub.

[@BackToBackSWE]

welcome aboard 🚢

[@pranavganorkar2379]

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 !

[@BackToBackSWE]

Nice, thx

[@pranavganorkar2379]

@@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

[@gajabchudakkarbaaz2657]

superb explanation 👍 In case of brute force approach if we also consider time taken to compare each and every generated window with string t then worst case time complexity should be o(n^3) right ?

[@BackToBackSWE]

I believe so, O(n^2) windows and O(n) time to search each one

[@gajabchudakkarbaaz2657]

Ok thanks!