🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤ This one turned out longer than expected, recommend 1.5x speed
Lmao I've watched so many lectures on youtube, many require you see it at 1.5x or 2x this is the first time, I have seen the youtuber himself suggesting doing the same, thank you for the uploads also can you do a question on union find algo?
I wonder if there's a problem in line 26~28. The "have" count is not balanced. Should we have the same == conditions as line 17? if s[l] in countT and windows[s[l]] == countT[s[l]]: have -= 1 windows[s[l]] -= 1 to make the count balanced. "have" is the number of unique characters that meets the required numbers.
"need" is number of unique characters in t, not total number of characters. I think the problem is in line 26~28, which should have the same == conditions as line 17. if s[l] in countT and windows[s[l]] == countT[s[l]]: have -= 1 windows[s[l]] -= 1 to make the count balanced. "have" is the number of unique characters that meets the required numbers.
In his solution, he set need = len(countT) instead of len(t), that makes the while loop( have == need) will execute with no errors. Of course we can set window[c]
thanks @felixdeng9824 that was the reason. in python len(dictionary) == number of keys. So the case of "aaa", the dictionary would be { "a": 3 } and the len(a) would be 1. That's why == works for neetcode!
I’m glad that somebody else had to watch it multiple times. Sometimes I just feel dumb, but I have to remind myself that these videos are prepared and Neetcode probably struggled with it himself at first.
Nice. I figured out how we would need to slide the window, but was struggling with how to store it and check if it satisfies the t counts. This was the first leetcode hard I've tried and feel good that I got a majority of the idea down.
I agree. It was not as hard to actually figure out what was needed to solve the problem, but then when it came to implementing the solution, it got really hard and confusing. It was probably because we were trying to implement the brute force approach.
@NeetCode Thanks so much for the video! I enjoyed watching how you solved this problem. I wanted to point out that the Leetcode problem states that we are dealing with only the 26 lowercase characters in the English alphabet. As such, our hashmap would be a constant size. Therefore our hashmap would never grow to a size of 100 as stated. All your videos are awesome. I hope my comment is constructive and helpful!
Thanks to you and NeetCode 150 list, I was able to solve this hard problem on my own without peeking at your solution! The runtime sucked really bad, but it was nonetheless accepted. Hooray!
I'm at a point where I draft up my approach, then watch Neet explain the approach to see how I did. Then I draft up the code on my whiteboard, then watch how Neet writes the code. Feelin good!
This is one of a very few hard leetcode problems that I solved without any help. But indeed this video dives to the depth of the concept, watching to understand what other ways I could have solved it. Thanks!!
@@Andrew-dw2cj Depends on problem. If I get an idea of what would be the flow, then I just jump to code. Otherwise I will think, write a pseudo code and then proceed to coding.
It tooks me 12 hours to solve hard problem for the first time lol. I even use a linked list haha. And the runtime is bad but at least pass the test. I always look at your solution after I try by myself and... I often learn something new. Thanks 👍
With new test case of s = "bbaa" , t = "aba", it's not going inside while loop because "need" end up to 3 and "have" end up with 2, Since we check for map values of currentChar, which is updating have to 3, but need is at 3, because of length of t, it has 3 as value so we need to update "need" = uniqueCharactersOf(t); which we can achieve using set
Thanks for another greater video ! after watching your video on 567. Permutation in String, I could figure out solution for this by myself. ur videos are always very inspiring and helpful ! also, just want to share how I handle the left position differently: 1. keep the left pointing at a char in t, 2. if countS[nums[l] ] > countT[nums[l] ], increase the left because we can shorten the substring by making left pointing at the next num in t these condition will make sure that redundant elements on the left are dropped before we calculate the len of current substring
Great Explanation, Thanks for everything! a small note: if we checked the entire hashmap, it will also be in O(1) because we have just lowercase and uppercase characters (Just 52 entries in the hashmap).
agreed, I think something like this works just as well (at least it passes on LC) class Solution: def minWindow(self, s: str, t: str) -> str: t_counts = {} w_counts = {} #window_counts for c in t: t_counts[c] = t_counts.get(c, 0) + 1 w_counts[c] = 0
l = 0 r = 0 def is_good_window(): for c in t_counts: if w_counts[c] < t_counts[c]: return False return True
curr_len = len(s) + 1 res = "" while r < len(s): w_counts[s[r]] = w_counts.get(s[r], 0) + 1
while is_good_window(): if r - l + 1 < curr_len: curr_len = r - l + 1 res = s[l:r+1] w_counts[s[l]] -= 1 l += 1 r += 1 return res
Another issue. In your code, the window map also count the character which does not exist in T, which is different from what you explained in slides. AFAK, your implementation is different than what you explained, though both of them are sliding window.
I was going to point out the same. In both push (for right char) and pop (for left char) places, we need to just push the chars that exist in t-map. And this code modification works perfectly according to his explanation. PS. Thank you so much Neetcode for this great video!
this is my modified solution using the explanation, the curr hashmap is a map of the chars in T all set to 0, and chars not in T are not added from S class Solution: def minWindow(self, s: str, t: str) -> str: tcount = collections.Counter(t) curr = {k : 0 for k in t} l = 0 have = 0 need = len(tcount) minlen = float('inf') res = [0,0]
for r in range(len(s)): if s[r] in curr: curr[s[r]] += 1 if curr[s[r]] == tcount[s[r]]: have += 1 while have == need: if (r - l + 1) < minlen: minlen = min(minlen, r - l + 1) res = [l,r]
if s[l] in curr: curr[s[l]] -= 1 if curr[s[l]] < tcount[s[l]]: have -= 1 l += 1
If String t has repeated characters, then instead of have+= 1 we can do have += countT[c] and similarly instead of have -= 1, we do have -= countT[s[l]]
Glad you made this solution video. I felt like i was close but wasn't able to test all the test cases. My approach was slightly off by trying to perform the solution with a single hashmap. Made some of the conditionals/updating super confusing and complicated and would have not finished in a real interview.
thanks for this! so in this case, have represents the number of characters needed to build substring t? i.e., we take into account duplicates when counting too.
"need" is number of unique characters in t, not total number of characters. I think the problem is in line 26~28, which should have the same == conditions as line 17. if s[l] in countT and windows[s[l]] == countT[s[l]]: have -= 1 windows[s[l]] -= 1 to make the count balanced. "have" is the number of unique characters that meets the required numbers.
To optimize our window shrinking process, I think we can store the index of the new valid value. This way, next time we can move our start point directly to the next valid value and begin counting from there.
I suggest an alternative solution, which I think it is far easier to understand and code. 1. Start defining a goal dictionary (with counts of "t" string) and worst dictionary (with counts of "s" string) -> current solution. 2. Check if solution valid (counts in goal smaller or equal to current solution) => solution exists, else return "". 3. Initiate a while loop with pointer l, r = 0, len(s) -1 3a If utmost left character not in goal, increase l. 3b Elseif utmost left character in goal and its count in current solution bigger than in goal, increase l and reduce count in current solution by 1 3c,3d elseif ... (analog for utmost right character) 3e return s[l:r+1] 4 return s[l:r+1]
Much simpler solution: keep incrementing the left pointer as long as the substr cond is satisfied.. Also don't worry about comparing the 2 dicts, its still O(1). def minWindow(self, s: str, t: str) -> str: cond = lambda c1, c2: all([c1.get(k, 0) >= c2[k] for k in c2]) sCounts = defaultdict(int) tCounts = dict(Counter(t)) minWindowSz = float('inf') minWindowIdx = 0, 0 L = 0 for R in range(len(s)): sCounts[s[R]] += 1 while cond(sCounts, tCounts) and L 0: sCounts[s[L]] -= 1 L += 1 return s[minWindowIdx[0]:minWindowIdx[1]+1] if minWindowSz < float('inf') else ""
Hey! Big fan here. Just wanted to point out, this code will fail for s= "bbaa" and t="aba" (Leetcode testcase). In line#17, you have the following (C# version) if (countT.find(c) != countT.end() && window[c] == countT[c]) For the aforementioned test scenario, countT['a'] is 2, while looping through s, for the first time when it sees 'a', window[c] == countT[c] this part of the statement will become false, hence have will not be increased. After finishing the first for loop, count will be 3 and have will be 2. If there are 10 'a's in s and 10 'a's in t, the have will have 1 after the loop. Therefore it'll return an empty string "". Changing it to following will pass the case. window[c]
Why does the need variable at 19:22 is set to count the unique characters only and not the count/num of occurrence of chars? It's because the windowCount map[s[l]] has >= count[s[l]] i.e during the comparison we will take care of the count. If t has "aaa" then step 1 is to check if string s has 'a' or not, later by imposing >= we make sure that sliding window has equal or greater occurrence of chars.
The time complexity should be O(n + k) instead of O(n), where k is the length of t. This is because in the beginning of the code we iterate over t to count its letter frequency.
It's a good solution, but I think it's very unlikely anyone could come up with the have, need variables in an interviewing first time seeing this problem. That is a very clever optimization.
Difficult to image that someone would genuinely come up with the solution on the fly. Only if one have solved exactly this problem before. So, what companies like Google are looking for --- diligent applicants who solve 200-300-400-500+ problems on leetcode and memorize approaches? I got my job in the startup this way. I solved about 80 the most popular problems on leetcode. And on the interview I got 2 out of 3 which I solved perfectly, and the 3-rd one(which I didn't see before) I solved in a brute-force way. That was enough to get in. So for Google, Facebook, etc. you just need to solve more, especially hard ones. That's it!
Hi Alexis Which questions did you solve? I am going to interview for google next month. Your input would be great. Even if you see this message later than a month, do reply, it might help someone else. Thanks
19:46 - why are we updating window hash map before checking if that character is in countT hash map? Aren't we only storing and counting characters we need and not ALL characters?
Amazing video with a great efficient solution, despite the code being a little bit all over the place at first glance I could perfectly follow your explanation great job!
Instead of maintaining a set for visited nodes, we can just mark a visited node as 0 and we can then skip it the next time. This spaces us the space complexity involved with the set.
I improved upon this by using a single hash map containing the amount of characters in the t string, and decrementing the value as it was encountered in s. As we closed the window, we would re increment back up. If all the values in the map were 0 or less, we knew we had a valid solution.
On line 10, it should be "have, need = 0, sum(countT.values())" because if a character is present more than once in t, then it is not enough to check the length of the dictionary (number of keys) but you would need to sum up the dict's values.
I was so close on this one! I didn't think of that have vs need thing you did so I only solved half the test cases because I moved the left pointer properly but only changed the min_window_size when the count in t matched the count in s, which failed cases where we had duplicates. I couldn't think of a quick way to compare that we have enough of each specific value in the "s" hashmap such that we could check to see if our window was smaller. I was thinking maybe you would just have to make a helper function to go through the "s" hashmap's keys and make sure you have at least enough of each letter to match the count in t, but making a single integer increment when you have enough for each key is smart. I didn't even bother implementing my hashmap count helper function because I figured I was missing some way of tracking the size of the s and t hashmap and didn't want to spend 20 minutes just to get to a TLE. *Edit: I actually did check to see how slow my helper function would be and it was 80% slower than NC's solution. So it could work to check through the hashmaps key by key each time, but it's super slow. Good to know I was really very close to solving this.
Skipping the coding solution part for now. I watched the explanation but it still seems worth it to try to code it on my own first, because it was a bit abstract.
Should line 27 be: if s[l] in countT and window[s[l]] + 1 == countT[s[l]]: ? Otherwise, if we try to shrink the window twice with the same left character, the "have" would be decremented twice for the same character?
I realized once "have" is decremented, the while condition of "have == need" would fail. So "have" would not be decremented more than once for the same character during any one window shrink operation.
doing java in interviews always messes me up, I get so caught up in trying to figure out how to do the little things :/ I tried switching to Python for that, but that messed me up too trying to learn a different language
Thank you for the video! It helps a lot! I think they might have updated the constraints. It is guaranteed that the length of s and t is >= 1 as of 11/3/22, so it is not necessary to check the edge case where t is empty now.
excellent explanation as always. i wonder how can someone come up with this solution in an actual interview of 45 min if it's a totally new problem?!!!
Instead of left, and right I was saving the substring in a string variable, that solution gave me memory error, but when using left and right It gives the correct answer, I am curious of how much extra overhead that might be adding that a new variable which cant be greater then the length s, is giving for a memory error
Thanks for this! Even though I understood how this particular problem is solved, I am not able to get the "intuition" or "trick" of this approach for some reason.
Hi neetcode, One question Suppose s = "ACDFCA and t = FCA. if we have found one window "ACDF" which contains "FCA". Can't we just start our window from "F" instead of going through "CDF..." Since we know our shortest window will always start from there only. btw thanks for the clear explaination as usual.
I think we cannot. Suppose s = "ADCAFCEA" and t = "FCA". If we have found one window "ADCAF", the next minimum window found would be "CAF". If we just start our window from "F" we miss that window.
Does this particular technique has any name? I mean how the two hashmaps are being compared without going through all the elements? This optimization technique seems so cool.
Also, isn't your solution O(n+m) because you're creating a hashmap for the smaller string which is M long. I had a doubt, isn't the bruteforce solution also just O(56*N+M) and it also reduces ultimately to O(N+M)? but yeah, ofcourse it isnt' at all optimised, but doesn't that satisfy the paramters of the follow up asked in the description?
Thanks for your videos, actually you do a great explanation, I have one doubt about this problem what if we have two results and print the result lexicographically which is smaller. if possible can you add this part? Thanks in advance
Hi NeetCode. Your video is amazing and helped so much in some problems that i did not have any idea to solve. By the way, when you apply in GG, are there any other questions related about System Design or something like that?
hey have one question how is your code working for test case "aa" "aa". since in that case has will only be updated once and hence result will not be updated ? I was able to submit by modifying my condition to increment have.
from collections import Counter def minimum_window(str1,str2): window="a"*(len(str1)+1) left=0 count=0 hashmap=Counter(str2) for i in range(len(str1)): if str1[i] in hashmap: hashmap [str1[i]]-=1 if hashmap [str1[i]]>=0: count+=1 while count==len(str2): if len(str1[left:i+1]) < len(window): window=str1[left:i+1] if str1[left] in hashmap: hashmap [str1[left]]+=1 if hashmap [str1[left]]>0: count-=1 left+=1 return window str1='ADOBECODEBANC' str2='ABC' print(minimum_window(str1,str2)) str1 = "PRWSOERIUSFK" str2 = "OSU" print(minimum_window(str1,str2))
I think this solution is failing test cases with duplicate letters in t. For example, s="aa" and t="aa". When you reach 2 a's, your 'have' variable becomes 1, but with 'need' set to length of t, that variable is 2 and they will never be equal.
Great explanation! Btw shouldn't `need` be sum of all values in `countT`. Otherwise, duplicates letters in String T will not be considered in the have == need matches.
🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤
This one turned out longer than expected, recommend 1.5x speed
Lmao I've watched so many lectures on youtube, many require you see it at 1.5x or 2x
this is the first time, I have seen the youtuber himself suggesting doing the same,
thank you for the uploads
also can you do a question on union find algo?
I wonder if there's a problem in line 26~28. The "have" count is not balanced. Should we have the same == conditions as line 17?
if s[l] in countT and windows[s[l]] == countT[s[l]]:
have -= 1
windows[s[l]] -= 1
to make the count balanced. "have" is the number of unique characters that meets the required numbers.
to be honest if I meet you and I hear you talking at normal speed, I would think you have dementia or something. I watch all your videos at 2x speed.
I never thought I'd see the day I'd fully understand a Leetcode Hard problem in under a half hour. Bless you sir.
same feeling 🥳
Beautiful..! The blackboard explanation, clean code, the naming conventions, everything is just beautiful. Thank you.
For your solution, in line 17 comparing both map counts:
if c in countT and window[c] == countT[c]
I had to replace == with
Thanks! This helps
same here!
"need" is number of unique characters in t, not total number of characters. I think the problem is in line 26~28, which should have the same == conditions as line 17.
if s[l] in countT and windows[s[l]] == countT[s[l]]:
have -= 1
windows[s[l]] -= 1
to make the count balanced. "have" is the number of unique characters that meets the required numbers.
In his solution, he set need = len(countT) instead of len(t), that makes the while loop( have == need) will execute with no errors. Of course we can set window[c]
thanks @felixdeng9824 that was the reason. in python len(dictionary) == number of keys. So the case of "aaa", the dictionary would be { "a": 3 } and the len(a) would be 1. That's why == works for neetcode!
Thank you for these videos! I'm switching from java to python for interviews and these have been really helpful
Thanks! I'm really happy that they are helpful!
Likely the most difficult question for sliding window. Again, watched it 3 times. Thank you, Neet!
wait till you try Sliding window Maximum.
@@Notezl 😂
I’m glad that somebody else had to watch it multiple times. Sometimes I just feel dumb, but I have to remind myself that these videos are prepared and Neetcode probably struggled with it himself at first.
tbh honest Sliding window Maximum way easier haahahah@@Notezl
Nice. I figured out how we would need to slide the window, but was struggling with how to store it and check if it satisfies the t counts. This was the first leetcode hard I've tried and feel good that I got a majority of the idea down.
I agree. It was not as hard to actually figure out what was needed to solve the problem, but then when it came to implementing the solution, it got really hard and confusing. It was probably because we were trying to implement the brute force approach.
as usual, your explanation makes a hard problem look simple! Thank you so much!
@NeetCode Thanks so much for the video! I enjoyed watching how you solved this problem. I wanted to point out that the Leetcode problem states that we are dealing with only the 26 lowercase characters in the English alphabet. As such, our hashmap would be a constant size. Therefore our hashmap would never grow to a size of 100 as stated. All your videos are awesome. I hope my comment is constructive and helpful!
That's not the case. Even at the beginning of the video it is seen that letters are capital.
great video, you're helping out a ton for interviews! Your channel is too underrated
Thanks to you and NeetCode 150 list, I was able to solve this hard problem on my own without peeking at your solution! The runtime sucked really bad, but it was nonetheless accepted. Hooray!
I'm at a point where I draft up my approach, then watch Neet explain the approach to see how I did. Then I draft up the code on my whiteboard, then watch how Neet writes the code. Feelin good!
This is one of a very few hard leetcode problems that I solved without any help. But indeed this video dives to the depth of the concept, watching to understand what other ways I could have solved it. Thanks!!
do you usually draw out a diagram and plan everything out before solving or do you just dive straight into the problem?
@@Andrew-dw2cj Depends on problem. If I get an idea of what would be the flow, then I just jump to code. Otherwise I will think, write a pseudo code and then proceed to coding.
@@SanketBhat7 how long have you been doing leetcode for you to be able to just jump straight into the code?
Had been in leetcode platform for more than 2 years but never had been this consistent. Recently started a consistent streak of 2+ months
It tooks me 12 hours to solve hard problem for the first time lol. I even use a linked list haha. And the runtime is bad but at least pass the test.
I always look at your solution after I try by myself and... I often learn something new. Thanks 👍
With new test case of s = "bbaa" , t = "aba", it's not going inside while loop because "need" end up to 3 and "have" end up with 2,
Since we check for map values of currentChar, which is updating have to 3, but need is at 3, because of length of t, it has 3 as value
so we need to update "need" = uniqueCharactersOf(t);
which we can achieve using set
I made this change and it worked thank you!
Thanks for another greater video ! after watching your video on 567. Permutation in String, I could figure out solution for this by myself.
ur videos are always very inspiring and helpful !
also, just want to share how I handle the left position differently:
1. keep the left pointing at a char in t,
2. if countS[nums[l] ] > countT[nums[l] ], increase the left because we can shorten the substring by making left pointing at the next num in t
these condition will make sure that redundant elements on the left are dropped before we calculate the len of current substring
Were you able to code it yourself?
C++ Implementation of the above explanation:
string minWindow(string s, string t) {
if(t==""){
return "";
}
unordered_map um;
for(int i=0;i
Thanks , this helps .
Helped a lot
7:56 Comparing the maps It wouldn't be bounded by t, it would be bounded by the number of possible characters, which is 52, or O(1).
I agree code needs one modification where you count need
this might be submitted, but in an interview, this solution will considered much much better, i think
Great Explanation, Thanks for everything!
a small note: if we checked the entire hashmap, it will also be in O(1) because we have just lowercase and uppercase characters (Just 52 entries in the hashmap).
agreed, I think something like this works just as well (at least it passes on LC)
class Solution:
def minWindow(self, s: str, t: str) -> str:
t_counts = {}
w_counts = {} #window_counts
for c in t:
t_counts[c] = t_counts.get(c, 0) + 1
w_counts[c] = 0
l = 0
r = 0
def is_good_window():
for c in t_counts:
if w_counts[c] < t_counts[c]:
return False
return True
curr_len = len(s) + 1
res = ""
while r < len(s):
w_counts[s[r]] = w_counts.get(s[r], 0) + 1
while is_good_window():
if r - l + 1 < curr_len:
curr_len = r - l + 1
res = s[l:r+1]
w_counts[s[l]] -= 1
l += 1
r += 1
return res
Another issue. In your code, the window map also count the character which does not exist in T, which is different from what you explained in slides. AFAK, your implementation is different than what you explained, though both of them are sliding window.
no, I think the implementation matches the code. Try and pop from left. If the character popped is not in 't', it throws a key error
I was going to point out the same.
In both push (for right char) and pop (for left char) places, we need to just push the chars that exist in t-map.
And this code modification works perfectly according to his explanation.
PS. Thank you so much Neetcode for this great video!
this is my modified solution using the explanation, the curr hashmap is a map of the chars in T all set to 0, and chars not in T are not added from S
class Solution:
def minWindow(self, s: str, t: str) -> str:
tcount = collections.Counter(t)
curr = {k : 0 for k in t}
l = 0
have = 0
need = len(tcount)
minlen = float('inf')
res = [0,0]
for r in range(len(s)):
if s[r] in curr:
curr[s[r]] += 1
if curr[s[r]] == tcount[s[r]]:
have += 1
while have == need:
if (r - l + 1) < minlen:
minlen = min(minlen, r - l + 1)
res = [l,r]
if s[l] in curr:
curr[s[l]] -= 1
if curr[s[l]] < tcount[s[l]]:
have -= 1
l += 1
if minlen == float('inf'):
return ""
l,r = res
return s[l:r+1]
If String t has repeated characters, then instead of have+= 1 we can do have += countT[c] and similarly instead of have -= 1, we do have -= countT[s[l]]
Glad you made this solution video. I felt like i was close but wasn't able to test all the test cases. My approach was slightly off by trying to perform the solution with a single hashmap. Made some of the conditionals/updating super confusing and complicated and would have not finished in a real interview.
398 ms done. Took me 40 minutes to do so. but now lets see optimised version too :)
I love how he explains and codes stuff elegantly !
The legend comes and make it a piece of cake as usual.
Your explanations are way more on another level.
thanks man.
whenever I find your video for a question I'm looking for, happiness = float("inf") !!
I didn't do this in Python but another language. There seems to be an issue with line 16. The condition should be checking if window[c]
yes, you're right! else, the test s = "aa" t = "aa" won't pass
thats true, thank youuu!
Was watching this on the neetcode site, literally opened it up to scan the comments for this issue cause I was doing this with JS lol.
thanks for this! so in this case, have represents the number of characters needed to build substring t? i.e., we take into account duplicates when counting too.
Hello, Bob Ross!. Amazing explanation as always :)
thanks for explaining in this simple words, otherwise people had made this question so hard and complex
Shouldn't line 17 be " if c in countT and window[c]
Same question had. Watch from 13:48 . Should help you.
need = len(countT) but not the len of String t, that takes care of duplicated char
Thank you pavan
"need" is number of unique characters in t, not total number of characters. I think the problem is in line 26~28, which should have the same == conditions as line 17.
if s[l] in countT and windows[s[l]] == countT[s[l]]:
have -= 1
windows[s[l]] -= 1
to make the count balanced. "have" is the number of unique characters that meets the required numbers.
I had this solved intuitively, in quadratic time i'm guessing which is why it was failing the last test case on Time. This is a great explanation 👍
you can check dictionary sizes if we treat absence as zero. Complexity remains same but less no variables
To optimize our window shrinking process, I think we can store the index of the new valid value. This way, next time we can move our start point directly to the next valid value and begin counting from there.
I suggest an alternative solution, which I think it is far easier to understand and code.
1. Start defining a goal dictionary (with counts of "t" string) and worst dictionary (with counts of "s" string) -> current solution.
2. Check if solution valid (counts in goal smaller or equal to current solution) => solution exists, else return "".
3. Initiate a while loop with pointer l, r = 0, len(s) -1
3a If utmost left character not in goal, increase l.
3b Elseif utmost left character in goal and its count in current solution bigger than in goal, increase l and reduce count in current solution by 1
3c,3d elseif ... (analog for utmost right character)
3e return s[l:r+1]
4 return s[l:r+1]
Much simpler solution: keep incrementing the left pointer as long as the substr cond is satisfied.. Also don't worry about comparing the 2 dicts, its still O(1).
def minWindow(self, s: str, t: str) -> str:
cond = lambda c1, c2: all([c1.get(k, 0) >= c2[k] for k in c2])
sCounts = defaultdict(int)
tCounts = dict(Counter(t))
minWindowSz = float('inf')
minWindowIdx = 0, 0
L = 0
for R in range(len(s)):
sCounts[s[R]] += 1
while cond(sCounts, tCounts) and L 0:
sCounts[s[L]] -= 1
L += 1
return s[minWindowIdx[0]:minWindowIdx[1]+1] if minWindowSz < float('inf') else ""
At 19:17 why is need set to size of countT? If t is "aab" then we would need 2 a and 1b right? But ur code will set need at 2
Keep posting videos regularly brother❤
I was asked this in an interview yesterday
I hate how clear you make things lol, like I had an idea, but then once I heard you talk about it, I figured it out
Awesome! Now I am going to code this in Java 🙂
Hey! Big fan here.
Just wanted to point out, this code will fail for s= "bbaa" and t="aba" (Leetcode testcase).
In line#17, you have the following (C# version)
if (countT.find(c) != countT.end() && window[c] == countT[c])
For the aforementioned test scenario, countT['a'] is 2, while looping through s, for the first time when it sees 'a', window[c] == countT[c] this part of the statement will become false, hence have will not be increased. After finishing the first for loop, count will be 3 and have will be 2. If there are 10 'a's in s and 10 'a's in t, the have will have 1 after the loop. Therefore it'll return an empty string "". Changing it to following will pass the case.
window[c]
since we're dealing with capital letters (assuming thats all we have to check) the maximum number of checks is 26, its not dependent on the size of t.
Why does the need variable at 19:22 is set to count the unique characters only and not the count/num of occurrence of chars?
It's because the windowCount map[s[l]] has >= count[s[l]] i.e during the comparison we will take care of the count. If t has "aaa" then step 1 is to check if string s has 'a' or not, later by imposing >= we make sure that sliding window has equal or greater occurrence of chars.
When it runs, it runs like Rolex, so intriguing and accurate! There are two windows actually: the l r and have need.
The time complexity should be O(n + k) instead of O(n), where k is the length of t.
This is because in the beginning of the code we iterate over t to count its letter frequency.
Thanks a lot for the amazing explanation with each video. It has been so useful to understand things.
It's a good solution, but I think it's very unlikely anyone could come up with the have, need variables in an interviewing first time seeing this problem. That is a very clever optimization.
Difficult to image that someone would genuinely come up with the solution on the fly. Only if one have solved exactly this problem before. So, what companies like Google are looking for --- diligent applicants who solve 200-300-400-500+ problems on leetcode and memorize approaches? I got my job in the startup this way. I solved about 80 the most popular problems on leetcode. And on the interview I got 2 out of 3 which I solved perfectly, and the 3-rd one(which I didn't see before) I solved in a brute-force way. That was enough to get in. So for Google, Facebook, etc. you just need to solve more, especially hard ones. That's it!
Hi Alexis
Which questions did you solve?
I am going to interview for google next month. Your input would be great.
Even if you see this message later than a month, do reply, it might help someone else.
Thanks
Took me two hours to solve this before watching your video gosh
19:46 - why are we updating window hash map before checking if that character is in countT hash map? Aren't we only storing and counting characters we need and not ALL characters?
Thank you for showing why we need that extra variable on top of hashmap & also that it will only be updated if it is ==
I solved this by myself, before seeing this solution. And I checked here to know that it was the most optimal solution :)
you can use Counter(t) to avoid the first loop
I wan't able to figure out how to reduce complexity from O(n*k) to O(n). Thank you for explaining the trick so easily!
Amazing video with a great efficient solution, despite the code being a little bit all over the place at first glance I could perfectly follow your explanation great job!
Phenomenal explanation !!!! Thank you sooo very much !!!
Best explanation ever. Thank you neetcode
Instead of maintaining a set for visited nodes, we can just mark a visited node as 0 and we can then skip it the next time. This spaces us the space complexity involved with the set.
Thank you very much~ It is really helpful~
I improved upon this by using a single hash map containing the amount of characters in the t string, and decrementing the value as it was encountered in s. As we closed the window, we would re increment back up. If all the values in the map were 0 or less, we knew we had a valid solution.
checking the whole map for 0 or less --> will take 0(m). In the video, the approach has 0(1) time complexity
so beautifully explained ❤❤❤
On line 10, it should be "have, need = 0, sum(countT.values())" because if a character is present more than once in t, then it is not enough to check the length of the dictionary (number of keys) but you would need to sum up the dict's values.
beautiful explanation as always
I was so close on this one! I didn't think of that have vs need thing you did so I only solved half the test cases because I moved the left pointer properly but only changed the min_window_size when the count in t matched the count in s, which failed cases where we had duplicates.
I couldn't think of a quick way to compare that we have enough of each specific value in the "s" hashmap such that we could check to see if our window was smaller. I was thinking maybe you would just have to make a helper function to go through the "s" hashmap's keys and make sure you have at least enough of each letter to match the count in t, but making a single integer increment when you have enough for each key is smart.
I didn't even bother implementing my hashmap count helper function because I figured I was missing some way of tracking the size of the s and t hashmap and didn't want to spend 20 minutes just to get to a TLE.
*Edit: I actually did check to see how slow my helper function would be and it was 80% slower than NC's solution. So it could work to check through the hashmaps key by key each time, but it's super slow. Good to know I was really very close to solving this.
Thanks bro ,I am keeping watching your video these days. I feel I am improving in a fast speed.
Whoa, it's something I'd never have come up with by myself 🔥
def was given this at google
did u slay ?
Skipping the coding solution part for now. I watched the explanation but it still seems worth it to try to code it on my own first, because it was a bit abstract.
Thank you for your detailed explanation on the approach!
Should line 27 be: if s[l] in countT and window[s[l]] + 1 == countT[s[l]]: ?
Otherwise, if we try to shrink the window twice with the same left character, the "have" would be decremented twice for the same character?
I realized once "have" is decremented, the while condition of "have == need" would fail. So "have" would not be decremented more than once for the same character during any one window shrink operation.
one more optimization that we can do is to skip sliding the window once the size becomes equal to the current minimum window size in the result.
What if this time we can shrink to even minimum window size - 1
Can anyone tell me why we don't need to initialize the right pointer ? Just doing for r in range(Len(s)) is enough ? I'm a bit confused
This was so so fun lol. You're doing the lord's work
During your explanation you missed listing CODEBA as another substring of length 6
doing java in interviews always messes me up, I get so caught up in trying to figure out how to do the little things :/ I tried switching to Python for that, but that messed me up too trying to learn a different language
Thank you for the video! It helps a lot! I think they might have updated the constraints. It is guaranteed that the length of s and t is >= 1 as of 11/3/22, so it is not necessary to check the edge case where t is empty now.
excellent explanation as always. i wonder how can someone come up with this solution in an actual interview of 45 min if it's a totally new problem?!!!
It is very clear for a hard leetcode problem.
Best explanation ever for this question, thank you for the great work!
Instead of left, and right I was saving the substring in a string variable, that solution gave me memory error, but when using left and right It gives the correct answer, I am curious of how much extra overhead that might be adding that a new variable which cant be greater then the length s, is giving for a memory error
Thanks for this! Even though I understood how this particular problem is solved, I am not able to get the "intuition" or "trick" of this approach for some reason.
Very nicely explained the hard problem. Really liking your videos. Thanks for this...
24:55 is not an off by one "error"... substring is just non-inclusive for end of range
I was able to come up with an idea of solving this, just did not know how to implement it in code.
Lord NeetCode SUPREME Teacher !!
thank you for the crystal clear explanation and code
man... is so hard to follow using this small variables, c, s, r, p , z, x...
Wow that was incredibly explained. Hats off once again.
You are such a good trainer
Hi neetcode, One question Suppose s = "ACDFCA and t = FCA. if we have found one window "ACDF" which contains "FCA". Can't we just start our window from "F" instead of going through "CDF..." Since we know our shortest window will always start from there only. btw thanks for the clear explaination as usual.
Yeah exactly!! The code can be optimised more. You’ve probably use a first-in-first-out queue data structure
I think we cannot. Suppose s = "ADCAFCEA" and t = "FCA". If we have found one window "ADCAF", the next minimum window found would be "CAF". If we just start our window from "F" we miss that window.
Hi, Thanks for the explanation. I think in the implementation, line number 17, the condition should be window[c]
Does this particular technique has any name? I mean how the two hashmaps are being compared without going through all the elements? This optimization technique seems so cool.
Thank you NeedCode I got the entire idea of your solution!
Also, isn't your solution O(n+m) because you're creating a hashmap for the smaller string which is M long. I had a doubt, isn't the bruteforce solution also just O(56*N+M) and it also reduces ultimately to O(N+M)? but yeah, ofcourse it isnt' at all optimised, but doesn't that satisfy the paramters of the follow up asked in the description?
Thanks for your videos, actually you do a great explanation, I have one doubt about this problem what if we have two results and print the result lexicographically which is smaller. if possible can you add this part? Thanks in advance
Hi NeetCode. Your video is amazing and helped so much in some problems that i did not have any idea to solve.
By the way, when you apply in GG, are there any other questions related about System Design or something like that?
hey have one question how is your code working for test case "aa" "aa".
since in that case has will only be updated once and hence result will not be updated ?
I was able to submit by modifying my condition to increment have.
he is setting need to len(countT) not len(t) so in the case of "aa" need will be set to 1 but inside countT dict "a" index will have value 2.
from collections import Counter
def minimum_window(str1,str2):
window="a"*(len(str1)+1)
left=0
count=0
hashmap=Counter(str2)
for i in range(len(str1)):
if str1[i] in hashmap:
hashmap [str1[i]]-=1
if hashmap [str1[i]]>=0:
count+=1
while count==len(str2):
if len(str1[left:i+1]) < len(window):
window=str1[left:i+1]
if str1[left] in hashmap:
hashmap [str1[left]]+=1
if hashmap [str1[left]]>0:
count-=1
left+=1
return window
str1='ADOBECODEBANC'
str2='ABC'
print(minimum_window(str1,str2))
str1 = "PRWSOERIUSFK"
str2 = "OSU"
print(minimum_window(str1,str2))
I think this solution is failing test cases with duplicate letters in t. For example, s="aa" and t="aa". When you reach 2 a's, your 'have' variable becomes 1, but with 'need' set to length of t, that variable is 2 and they will never be equal.
Great explanation!
Btw shouldn't `need` be sum of all values in `countT`. Otherwise, duplicates letters in String T will not be considered in the have == need matches.
nah, `need` is the `n_unique_chars` in `t`. `need` isn't `n_chars` in `t`.