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

Пікірлер: 95

  • @christopherreyes3896
    @christopherreyes38963 жыл бұрын

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

  • @AlgosWithMichael

    @AlgosWithMichael

    3 жыл бұрын

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

  • @megatronislive1331
    @megatronislive13316 ай бұрын

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

  • @mehdiLesty
    @mehdiLesty2 жыл бұрын

    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
    @kevindebruyne173 жыл бұрын

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

  • @AlgosWithMichael

    @AlgosWithMichael

    3 жыл бұрын

    Haha yea he is a LeetCode master

  • @AlancRodriguez
    @AlancRodriguez2 жыл бұрын

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

  • @AlgosWithMichael

    @AlgosWithMichael

    2 жыл бұрын

    Thank you!

  • @sata1938
    @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.

  • @interviewprep6827
    @interviewprep68273 жыл бұрын

    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

    @AlgosWithMichael

    3 жыл бұрын

    Haha that is awesome, glad it was helpful

  • @kumarc4853
    @kumarc48533 жыл бұрын

    for harder problems we come to Michael

  • @afnanrehman866
    @afnanrehman8663 ай бұрын

    Thanks for the upload

  • @tylercondon3453
    @tylercondon34532 жыл бұрын

    very informative video thank you Michael

  • @juliahuanlingtong6757
    @juliahuanlingtong67573 жыл бұрын

    Greatest explanation and demonstration on sliding window!

  • @AlgosWithMichael

    @AlgosWithMichael

    3 жыл бұрын

    Thank you!

  • @mridulsetia4974
    @mridulsetia49742 жыл бұрын

    Awesome Explanation!! Thanks

  • @gouravbansal994
    @gouravbansal9943 жыл бұрын

    Great Video Man!

  • @williamzayas302
    @williamzayas3022 жыл бұрын

    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

    @AlgosWithMichael

    2 жыл бұрын

    I really appreciate that

  • @MsSkip60
    @MsSkip603 жыл бұрын

    Great explanation thanks! Loved the cat part :D

  • @AlgosWithMichael

    @AlgosWithMichael

    3 жыл бұрын

    Thank you very much! best comment

  • @tharunkumarreddy1224
    @tharunkumarreddy12242 жыл бұрын

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

  • @AlgosWithMichael

    @AlgosWithMichael

    2 жыл бұрын

    Thank you so much 😀

  • @hawaijarmayengbam4451
    @hawaijarmayengbam4451 Жыл бұрын

    Thank you, you made my day!

  • @hoangchungduyminh7568
    @hoangchungduyminh75682 жыл бұрын

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

  • @AlgosWithMichael

    @AlgosWithMichael

    2 жыл бұрын

    Thank you!

  • @CPAMJIO
    @CPAMJIO Жыл бұрын

    thank you so much!!! great explaination

  • @sitronco
    @sitronco3 жыл бұрын

    Great video. Thanks for the content

  • @AlgosWithMichael

    @AlgosWithMichael

    3 жыл бұрын

    My pleasure!

  • @Manishgupta200
    @Manishgupta20010 ай бұрын

    That's understable. Thankyou

  • @nayemalaboni8318
    @nayemalaboni83183 жыл бұрын

    new subscriber you explain very well

  • @B-Billy
    @B-Billy3 жыл бұрын

    Loved it.. Subscribed!

  • @AlgosWithMichael

    @AlgosWithMichael

    3 жыл бұрын

    Awesome! Thank you!

  • @ShashankRustagiCSE
    @ShashankRustagiCSE2 жыл бұрын

    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

    @AlgosWithMichael

    2 жыл бұрын

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

  • @ShashankRustagiCSE

    @ShashankRustagiCSE

    2 жыл бұрын

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

  • @jasonli6057
    @jasonli60572 жыл бұрын

    super helpful, first time comment in youtube

  • @gunahawk6893
    @gunahawk6893 Жыл бұрын

    glad i found ur channel

  • @HKCSFARJADAHMEDKHAN
    @HKCSFARJADAHMEDKHAN3 жыл бұрын

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

  • @AlgosWithMichael

    @AlgosWithMichael

    3 жыл бұрын

    Thank you!

  • @girlingame518
    @girlingame5183 жыл бұрын

    i subscribed because of your cat 😁 , great explanation

  • @AlgosWithMichael

    @AlgosWithMichael

    3 жыл бұрын

    Thank you!

  • @ellisbrown3539
    @ellisbrown35392 жыл бұрын

    Such a good video.

  • @AlgosWithMichael

    @AlgosWithMichael

    2 жыл бұрын

    Ayy thank you!

  • @abanerjee3704
    @abanerjee370411 ай бұрын

    Purrfect!

  • @yy-gf7ze
    @yy-gf7ze2 жыл бұрын

    You are always amazing AF.

  • @AlgosWithMichael

    @AlgosWithMichael

    2 жыл бұрын

    Haha I appreciate that

  • @tjalferes
    @tjalferes2 жыл бұрын

    Thank you.

  • @happyl4463
    @happyl44633 жыл бұрын

    I was totally distracted by your cat lol

  • @AlgosWithMichael

    @AlgosWithMichael

    3 жыл бұрын

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

  • @tongwang535
    @tongwang5353 жыл бұрын

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

  • @AlgosWithMichael

    @AlgosWithMichael

    3 жыл бұрын

    Great suggestion!

  • @user-cw3jg9jq6d
    @user-cw3jg9jq6d4 ай бұрын

    where did you get the sound clip for the error?

  • @saulgoodman6710
    @saulgoodman6710 Жыл бұрын

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

  • @naliniprakash7738
    @naliniprakash77382 жыл бұрын

    Coolest Explaination

  • @Tamilsd629
    @Tamilsd6292 жыл бұрын

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

  • @boundlesstech5292
    @boundlesstech52922 жыл бұрын

    The smartest cat on the internet fasho 🙂 lol

  • @amansoni0922
    @amansoni09223 жыл бұрын

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

  • @AlgosWithMichael

    @AlgosWithMichael

    3 жыл бұрын

    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.

  • @jasonahn8658
    @jasonahn8658 Жыл бұрын

    Best explanation! But HOLY it's difficult haha

  • @aniruddhkarekar2818
    @aniruddhkarekar281810 ай бұрын

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

  • @manuelpineda924
    @manuelpineda924 Жыл бұрын

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

  • @piratesuman
    @piratesuman3 жыл бұрын

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

  • @AlgosWithMichael

    @AlgosWithMichael

    3 жыл бұрын

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

  • @kevinchou1522
    @kevinchou15222 жыл бұрын

    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

    @AlgosWithMichael

    2 жыл бұрын

    Haha yea. It is a challenging problem for sure

  • @sumitvaise5452
    @sumitvaise54522 жыл бұрын

    Simply and well put explanation. Thanks

  • @vinaysimha95
    @vinaysimha953 жыл бұрын

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

  • @AlgosWithMichael

    @AlgosWithMichael

    3 жыл бұрын

    Yea you are right haha, thanks for pointing that out

  • @____r72
    @____r72 Жыл бұрын

    Nice cat

  • @tusharsaini767
    @tusharsaini7672 жыл бұрын

    nyc code kitty

  • @amazingsaavya6268
    @amazingsaavya62683 жыл бұрын

    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?

  • @karthikVignesh-
    @karthikVignesh-10 ай бұрын

    i just cant take my eyese off from that cat

  • @rohinbisht9668
    @rohinbisht96682 жыл бұрын

    correction: min length is j - i + 1

  • @3pleFly
    @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
    @rohankumarshah56792 жыл бұрын

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

  • @gunahawk6893
    @gunahawk6893 Жыл бұрын

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

  • @shags91
    @shags91 Жыл бұрын

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

  • @kruthikasm2809
    @kruthikasm2809 Жыл бұрын

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

  • @alpati123
    @alpati1233 жыл бұрын

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

  • @shreyaprajapati969

    @shreyaprajapati969

    3 жыл бұрын

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

  • @ruhigarga9542

    @ruhigarga9542

    2 жыл бұрын

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

  • @gunahawk6893

    @gunahawk6893

    Жыл бұрын

    @@ruhigarga9542 +1

  • @thebluefox100
    @thebluefox100 Жыл бұрын

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

  • @gunahawk6893

    @gunahawk6893

    Жыл бұрын

    6-1 , 1-1

  • @niranjan08538
    @niranjan085382 жыл бұрын

    Quite confusing on updating minLength

  • @avinashsorab5026
    @avinashsorab50265 ай бұрын

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

  • @ramsescoraspe
    @ramsescoraspe10 ай бұрын

    remove lyft from your list!! 😉

  • @londrali8085
    @londrali80852 жыл бұрын

    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

    @AM-nv4ol

    Жыл бұрын

    i'm calling the police

  • @bigE595
    @bigE5953 жыл бұрын

    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

    @AlgosWithMichael

    3 жыл бұрын

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

Келесі