Minimum Window Substring | Sliding Window | LeetCode

Minimum window substring is a sliding window problem asked at Facebook, Amazon, Microsoft, Lyft, Google, LinkedIn, Apple, and Bloomberg. This problem is a hard problem that involves the use of several pointer and sliding window algorithm knowledge.
Check out my interview prep platform for learning the patterns!
📢 Interview Prep Platform: algoswithmichael.com
🔗 Social 🔗
🎧 Join the community Discord: / discord
💰 Support me on Patreon: / michaelmuinos
🔗Follow me on LinkedIn: / michael-muinos
📂Follow me on Github: github.com/MichaelMuinos
⭐️ Timestamps ⭐️
00:00 - Intro
00:09 - Problem Overview
01:29 - Algorithm Walkthrough
11:24 - Code Walkthrough
16:51 - Time & Space Complexity

[@christopherreyes3896]

I don’t usually comment but I want you to know these are very helpful, well explained, and entertaining! Thanks man.

[@AlgosWithMichael]

Thank you Chris! I'm not much of a commenter either when I am on KZbin as a viewer either haha so I appreciate that

[@megatronislive1331]

Cat !! The coder. Thank you catty for such a wonderful explanation

[@mehdiLesty]

I like the way you explain using algorithm walkthrough before coding (the coding part becomes naturally understandable since your first visual explanation is clear). Thumb smashed.

[@kevindebruyne17]

Wow can't believe this cat is solving LC hard problems! Purrfect interviewee.

[@AlgosWithMichael]

Haha yea he is a LeetCode master

[@AlancRodriguez]

I really like the visual effects you have implemented, not a lot of other KZbinrs have this

[@AlgosWithMichael]

Thank you!

[@sata1938]

Well done. I like that you spoke clearly, slowly and methodically. A lot of other similar types of videos have the narrator jumping around and explaining the solution on the fly. I really liked your intentional approach and how you visualized everything neatly.

[@tylercondon3453]

very informative video thank you Michael

[@interviewprep6827]

Very clear explanation.. Actually 2 days back I saw this question on leetcode and was searching your channel to find the video... U read my mind.. Thanks a lot...

[@AlgosWithMichael]

Haha that is awesome, glad it was helpful

[@kumarc4853]

for harder problems we come to Michael

[@mridulsetia4974]

Awesome Explanation!! Thanks

[@juliahuanlingtong6757]

Greatest explanation and demonstration on sliding window!

[@AlgosWithMichael]

Thank you!

[@gouravbansal994]

Great Video Man!

[@afnanrehman866]

Thanks for the upload

[@MsSkip60]

Great explanation thanks! Loved the cat part :D

[@AlgosWithMichael]

Thank you very much! best comment

[@williamzayas302]

This was really helpful! I tried different approaches, but couldn't solve it. A+ for editing. I know how long editing takes and sometimes it's hard. Thanks for step by step explanation. Keep up the good work!! 👍

[@AlgosWithMichael]

I really appreciate that

[@tharunkumarreddy1224]

U xplained it in a trivial way !!keep up the good work🙌

[@AlgosWithMichael]

Thank you so much 😀

[@hawaijarmayengbam4451]

Thank you, you made my day!

[@CPAMJIO]

thank you so much!!! great explaination

[@hoangchungduyminh7568]

Liked and subscribed. Well-informative video, my applause.

[@AlgosWithMichael]

Thank you!

[@nayemalaboni8318]

new subscriber you explain very well

[@sitronco]

Great video. Thanks for the content

[@AlgosWithMichael]

My pleasure!

[@Manishgupta200]

That's understable. Thankyou

[@B-Billy]

Loved it.. Subscribed!

[@AlgosWithMichael]

Awesome! Thank you!

[@jasonli6057]

super helpful, first time comment in youtube

[@gunahawk6893]

glad i found ur channel

[@ShashankRustagiCSE]

Honestly saying, I sighed when you said the most difficult to digest part of the algo is when we shrink the window and start incrementing when we find the characters in the map. You were right. Now i get the whole crux of the algorithm. This question was asked in Codenation(trilogy Innovation)

[@AlgosWithMichael]

Yeah it is pretty hard to conceptualize, looking at an animated example really helped

[@ShashankRustagiCSE]

@@AlgosWithMichael if you are on LinkedIn, please drop me your id

[@girlingame518]

i subscribed because of your cat 😁 , great explanation

[@AlgosWithMichael]

Thank you!

[@HKCSFARJADAHMEDKHAN]

best explanation you can fi0nd on youtube for this problem . Great job .

[@AlgosWithMichael]

Thank you!

[@yy-gf7ze]

You are always amazing AF.

[@AlgosWithMichael]

Haha I appreciate that

[@ellisbrown3539]

Such a good video.

[@AlgosWithMichael]

Ayy thank you!

[@tjalferes]

Thank you.

[@abanerjee3704]

Purrfect!

[@tongwang535]

Thank you very much! Could you talk about some design problems? like LRU

[@AlgosWithMichael]

Great suggestion!

[@happyl4463]

I was totally distracted by your cat lol

[@AlgosWithMichael]

He wouldn't move when I was about to film, so he had to do it :p

[@naliniprakash7738]

Coolest Explaination

[@Tamilsd629]

Great Job Mike!! If you share the code . it will be more helpful.

[@jasonahn8658]

Best explanation! But HOLY it's difficult haha

[@boundlesstech5292]

The smartest cat on the internet fasho 🙂 lol

[@manuelpineda924]

I got this as a coding challenge and failed it :( thank you if I ever encounter this I will be prepared now.

[@vinaysimha95]

Small correction. I think you meant to say, space complexity is O(M) not O(N). (The length of string T is M)

[@AlgosWithMichael]

Yea you are right haha, thanks for pointing that out

[@saulgoodman6710]

@7:10 around, why did you increase only count of A by 1 in the hasmap? why not other elements?

[@kevinchou1522]

The hard part of this problem for me was the recognizing and implementing backtracking optimization... which turns out can be done easily with a count variable haha

[@AlgosWithMichael]

Haha yea. It is a challenging problem for sure

[@user-cw3jg9jq6d]

where did you get the sound clip for the error?

[@sumitvaise5452]

Simply and well put explanation. Thanks

[@rohinbisht9668]

correction: min length is j - i + 1

[@karthikVignesh-]

i just cant take my eyese off from that cat

[@aniruddhkarekar2818]

You said we move i pointer forward to get rid of the useless characters from the prefix of our substring then why do we incremented the count at the 0th index which is character A and it should be present in the final answer ???

[@____r72]

Nice cat

[@tusharsaini767]

nyc code kitty

[@piratesuman]

If the string T was "ABBC" shouldn't the count be 4? map.size() would be 3, right?

[@AlgosWithMichael]

The count is the number of unique characters, so in that example it would still be 3.

[@amazingsaavya6268]

I have a question: do we have to face coding interview with experience level 18 years if someone is already working as architect. ? Which companies may do that?

[@shags91]

This doesn't work if you have t containing multiple same characters. Even if t = "aabc", this algorithm still returns "banc"

[@amansoni0922]

There is a nested while(), why is that not accounting for n^2 complexity ? Can anyone pls help me with that !

[@AlgosWithMichael]

Yea I understand why that is confusing. The while loop is moving our 2nd pointer to in the worst case touch each element one time. So in other words in the worst case, each pointer will touch each node 1 time making the time complexity (n + n) which is just n. Hope that makes sense.

[@3pleFly]

I didn't like that the first window size you gave is incorrect, ADOBEC is not 5 length, but 6! , I understand what you're doing but it seems strange to me.

[@rohankumarshah5679]

its not working fine in below test case s = "abc" ; t = "b" ;

[@kruthikasm2809]

This fails for case where s=aa and t=aa

[@gunahawk6893]

how come ur were not visible to me these day man , please when got time do dp problems

[@alpati123]

Its failing for the inputs as s = "aa" & t ="aa"

[@shreyaprajapati969]

needs to change on line 20: map.get(endChar) >= 0

[@ruhigarga9542]

Instead of initializing count = map.size(); you need to initialize count = t.Length();

[@gunahawk6893]

@@ruhigarga9542 +1

[@thebluefox100]

why is 1,6 a valid substring in your video at 7:28 ? it does not contain any 'A'

[@gunahawk6893]

6-1 , 1-1

[@niranjan08538]

Quite confusing on updating minLength

[@avinashsorab5026]

Who's here from Daily Question 2/3/24? :)

[@ramsescoraspe]

remove lyft from your list!! 😉

[@londrali8085]

I wanna have 3 copies of that cat. I wanna swallow the first one like a pill, lick the second one for years to come, and just pet the third one for about 12 hours a day. Good explanation, too.

[@AM-nv4ol]

i'm calling the police

[@bigE595]

For time complexity, you say N is length of string S and M is length of string T. For space complexity, you say N is length of string T. Was this a mistake? Why not keep the variable names consistent across time and space complexity? Thanks for the great video, enjoyed watching.

[@AlgosWithMichael]

Yea good point. I guess it is habit for me to N and M for time and space complexity explanations