🚀 neetcode.io/ - A better way to prepare for Coding Interviews
@adityavartak6990
3 жыл бұрын
Why did you pick sliding window approach.I didnt understand the thinking process of this algo selection
@sinnyman2157
3 жыл бұрын
well, great video, but i did not unerstand the last move - "r-l+1", could u explain
@igorverevkin7709
3 жыл бұрын
Could you please explain the last part (r-l+1). What did you mean by "we can make result larger than it is if the current window size is greater than it is right now"? Thanks!
@rajakrishna
3 жыл бұрын
@@igorverevkin7709 r-l+1 is the size of the current substring. l,r are indexes which means in "abc" index(c)-index(a) will give 2 instead of 3 that's why you add 1 to it
@bruce716
2 жыл бұрын
@@rajakrishna Thanks for the details.
@arunsp767
2 жыл бұрын
A very important correction. Not in the code, but in the explanation: We use Set NOT because it stores unique characters, but because (in HashSet) the operation 'contains()' runs in O(1). We really don't need a data structure that maintains unique elements because we are doing that part explicitly using the 'contains()' operation. So the code would run fine even with a regular List. But 'contains()' in List is typically O(n). Hence the choice of (Hash)Set
@zionroar9066
2 жыл бұрын
For that matter we could of used a dictionary, because look up in a dictionary is 0(1)
@user-us4mc7ej3c
Жыл бұрын
@@zionroar9066 but it takes more space than a set bc the keys. Always better to optimize time AND space complexity
@jaechanlee290
Жыл бұрын
@@user-us4mc7ej3c they are the same in terms of "space complexity".... O(N).
@dancingdragon1143
Жыл бұрын
@@jaechanlee290 No key value pairs use a hashing algorithm so that each key is unique. Therefore spacial complexity will alway be less optimal than say a list where elements can be stored contiguously. If your keys aren't sufficiently spaced you risk a key collision which will amortize your lookup time to 0(n) .
@dancingdragon1143
Жыл бұрын
I still don't understand. Our conditional checks every char in string s. our left pointer iterates based on each character. So are we not still o(n) given we're checking each element at o(1) time complexity?
@dilln2158
2 жыл бұрын
Amazing explanation as always. Just a little trick I found, instead of res = max(res, r - l + 1), we can simply do res = max(res, set.size()), because the size of the set at that point in the loop will be the size of the current substring
@brickndick
Жыл бұрын
Is that true? LC errors out when I call charSet.size()
@sk_4142
Жыл бұрын
@George standard implementation of size/len is O(1) time. The sizes/lengths of most data structures are usually kept as instance variables that can be retrieved and updated (when adding to or removing from, say, an array or a set) in constant time
@garyhu728
Жыл бұрын
@@brickndick If you're doing LC in Python, it should be len(charSet)
@wycliffeo4656
Жыл бұрын
This is good because i was wondering why we created a set id we are not using it in any determining operation
@MrjavoiThe
Жыл бұрын
That’s more understandable, r - l + 1 is confusing.
@mostinho7
Жыл бұрын
Done thanks! Sliding window vs two pointer, in sliding window we keep expanding and shrinking the window dynamically, by moving left and right pointers (sliding left side in this case to reduce the window size) until we don’t have duplicates in our window. Then we can increase window by moving right pointer. Algorithm: Expand window until you encounter a duplicate, then keep shrinking the window until the duplicate is not in the window anymore. Keep track of longest substring. Pitfall: - when shrinking the window, you have to remove the character from your Set data structure as well - when you encounter a duplicate when expanding the window, the duplicate that needs to be removed won’t necessarily be the one on the left end, it can be inside the window so you have to keep popping till you reach it
@vezzolter
Ай бұрын
Thank you! Quite a great summary, especially important for me was your note about last pitfall.
@douglasfrb
2 жыл бұрын
Hey dude! I really appreciate everything you've been doing with these videos teaching how to solve this algorithms. I have a good understanding of data structures in general but I never actually knew about some techniques that people use to solve these problems. I'm studying algos for almost a week now and when I come across with a complicated one and a I struggle to solve I always come here to see your point of view. Just a comment to show my gratitude.
@AnmolSingh-sb5jj
2 жыл бұрын
You're the best. Got selected at Amazon because of your teaching.
@abebts20000
Жыл бұрын
You could just use hashmap to store the last index of the character and just move you start of the sliding window to the character next to the duplicate one. Rather than erasing all the characters from set. int lengthOfLongestSubstring(string s) { unordered_mapdict; int mx =0; int start =0,end=0; for(;end
@The6thProgrammer
Жыл бұрын
This solution will fail on certain cases. For "abba" this returns 3 instead of 2. The approach will still work however, just update the conditional statement to check that dict[s[end]] >= start as well, so you ignore any indices out of the current sliding window. (e.g. if (dict.find(s[end]) != dict.end() && dict[s[end]] >= start).
@cesaralcantara1341
3 жыл бұрын
If you are having trouble understanding any parts, I would recommend writing the code in vs code and debugging it. Add some watch variables as well. Really helped me understand some parts of this algorithm. Great stuff man, really helpful!
@chilo7272
2 жыл бұрын
The debugger in leetcode does the same or is vscode better?
@pmxi
2 жыл бұрын
@@chilo7272 well, the vscode debugger is free
@MrMainak90
4 жыл бұрын
One of the cleanest solutions i have come across, thanks!!
@licokr
6 ай бұрын
all of a sudden, come to think of it, even though I'm watching this video to find the answer and how it works. I think this channel is not only talking about the answer of a coding interview problem. He is actually teaching people, not only telling us about an answer. I'mr really glad I found this channel. It helps me grow up as a software developer. I really hated algorithm but this channel makes me finding fun in solving problems. I really appreciate it with all of my heart.
@eddockery7118
3 жыл бұрын
alternatively you can use: res = max(res, len(found)) I think that maybe a bit cleaner and intuitive for some.
@ahmadyasser9317
2 жыл бұрын
what is "found" here?
@LeiN255
2 жыл бұрын
@@ahmadyasser9317 charSet
@dimakavetskyy2082
2 жыл бұрын
thanks that makes more sense to me
@admercs
2 жыл бұрын
Less space-time efficient though.
@chyyeeah
4 жыл бұрын
Appreciate the content! It might be useful at the end to do a quick summary and run through just to cement the idea. Thanks!
@letechnicaljames
2 жыл бұрын
If there is a duplicate, we need to continue to shift the leftmost pointer. Got it. And remove character from substring set. Sliding window technique is highly key to reduce time complexity to O(N) for substring/subarray problems.
@ciantim2996
Жыл бұрын
It's not 100% correct right ? I'm not sure in Python but I think Set is not guarantee order so removing left most character in set might lead incorrect result. For example: input: "bcabefg" -> expected result: 6 ('cabefg') At the point where r = 3, the set is now contains ('b', 'c', 'a) but since it's not ordered it might appear like 'cab', thus we gonna remove all the characters currently in the set and leads wrong result 4 (befg) Please correct me if something wrong
@namankothari8390
3 ай бұрын
I am also wondering the same thing, and trying to rack my brain to understand how is it removing items in an order. If you got to know how, please explain
@trebla22222
15 күн бұрын
@@namankothari8390 im not sure if you still need it but when we call charSet.remove(s[l]), we are looking for the char that matches s[l] in the set and removing it. remember that s is the string so s[l] is the leftmost from the string, not from the set. for example, when input: "bcabefg" and r = 3, the set now contains ('b', 'c', 'a). and yes it might appear like 'cab'. but when we remove(s[l]), we are not removing the left-most from the set but rather removing s[l] when l = 0, which is 'b'. thus the set will now be ('c', 'a'). hope this helps!
@pinakadhara7650
Жыл бұрын
Great explanation! I used dictionaries instead of set and moved the max comparison under an if condition so that it runs only when it comes across a duplicate character. It cut the runtime by almost 50%
@lelandconn
4 жыл бұрын
Why does changing the solution from "While s[r] in charSet" to "If s[r] in charSet" change the result for the scenario when string is "pwwkew"?
@suhailahmed2310
4 жыл бұрын
while will run until the condition becomes false, if just checks once and exits
@MIDNightPT4
2 жыл бұрын
if only checks if the left-most character is the same as the current, but this is not always the case. For example: BCAC . Once you reach the right-most C (our current character), an if statement will only remove one character: B. But if we do that, it becomes CAC, and there is still a duplicate. So we use the while loop to loop UNTIL the duplicate letter is gone.
@87frasta
2 жыл бұрын
@@MIDNightPT4 You saved my brain, that's exactly what I was trying to figure it out
@shwethaks7994
2 жыл бұрын
This solution does not work for test case 'pwwkew'. Any updates on why it doesn't pass.
@jhangtheman
2 жыл бұрын
Make sure you use a WHILE and not an IF on line 8. If you run into multiple duplicate characters like "ww" it only runs the if once, when in fact you need it run twice.
@rhen4610
2 жыл бұрын
Bruuuh i really got stuck for hours on this problem set and almost got 50 lines and this dude did it in 13 lines 😩😩😩😩😩
@jasonswift7468
Жыл бұрын
Using a hashtable to remeber the last index of every char, And keep tracking the starting point of a valid substring. That is a little bit fast compared to using a while loop.
@aurelianoyepez5107
3 жыл бұрын
one of the best algo/ds interview prep channels out there!!!!
@jigglypikapuff
Жыл бұрын
Thanks a lot, great as always! I believe we can slightly improve by using the hashmap, instead of the set, to also keep track of the index where the character appeared last time so that we can instantly move the left pointer past that index, once the duplicate is found.
@xyz-vv5tg
11 ай бұрын
Can you please provide the code using hashmap?
@jigglypikapuff
11 ай бұрын
@@xyz-vv5tg More or less l = 0 duplicates = {} max_length = 0 for r in range(len(s)): if duplicates.get(s[r], -1) >= l: l = duplicates[s[r]] + 1 duplicates[s[r]] = r max_length = max(max_length, r - l + 1) return max_length
@Taranggpt6
7 ай бұрын
Can anyone help me to understand that why are we removing the left most character? aren't we supposed to remvoe the duplicate character which just came in while traversing? i.e. s[right]?? @neetcode
@Ba2sik
Ай бұрын
What I did, is storing in hashMap each character and its index. And then I check , if the left pointer is smaller than hash[letter], I set left = hash[letter] therefore skipping the inner while loop.
@rayhanmuktader1064
8 ай бұрын
I really like the way you explain things. One question though, is it safe to just remove the leftmost char from charSet since python set does not preserve any order? Can we be sure that the right characters are being removed?
@randomkoolstuff
2 жыл бұрын
Isn't it better to use a hashmap (or dictionary) to store the index? That way instead of using a while loop, you can have some additional logic to jump the left pointer. And if a character shows up in the hashmap but is behind the left pointer, we can simply update the index in the hashmap and recognize it as part of the string. The math for the distance would be based on the left and right pointers instead of the length of the hashmap.
@NeetCode
2 жыл бұрын
Yeah, I agree a hashmap is probably better in this case. That said, the worst-case time complexity should stay the same.
@randomkoolstuff
2 жыл бұрын
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: if len(s) == 0: return 0 seenCharacters = {} left = 0 right = 1 maxLen = 1 seenCharacters[s[left]] = left # For left, you do not need to go to the end. If right hits end, you # have already found the max length, checking from left to the end # is unnecessary even though there could be SMALLER valid substrings while right < len(s): newChar = s[right] # Checking if character is in the map and has to be greater than # left pointer. This is to allow the left pointer to jump/update without # having to delete/remove items from the hashmap if newChar in seenCharacters and seenCharacters[newChar] >= left: left = seenCharacters[newChar] + 1 else: # Only get max when no duplicates maxLen = max(right - left + 1, maxLen) # Continuously update the mapping, even if seen before since the new # location of the existing character is important for the if # condition above seenCharacters[newChar] = right right = right + 1 return maxLen
@randomkoolstuff
2 жыл бұрын
@NeetCode In the code above, wouldn't it be slightly faster? For example if you had "abcdefghijklmnoppabdce". You wouldn't need to delete every character from the set before p. You would simply jump the left pointer to where 'p' is first time you saw the duplicate in the substring + 1. The reason I do this and not just update to where the new duplicate character is because maybe there is a larger substring from that point. Let me know what you think. I would have thought maybe that though the speed increased, the drawback now is the space complexity since a little more space is needed (and not deleted) for the indexes.
@oluwatomilola
Жыл бұрын
@@randomkoolstuff hi! please why did you set the max length to be 1 initially in your code?
@chrischika7026
Ай бұрын
it isnt better
@atheerabdullatif7557
Жыл бұрын
the #2 while is not needed charSet = set() l = 0 c=0 big = 0 while(c
@bereketyisehak5584
Жыл бұрын
Space complexity should be o(1) as there are limited number of characters in the alphabet,
@shaikhevogen7811
Жыл бұрын
umm don't u think this will be O(N^2) since we have a nested loop here ?
@mistercosmin3542
4 жыл бұрын
I did hashset of chars+queue+sliding window technique, got 12 ms for C++(faster than 93%). Anyway clean and neat solution bro, congrats!
@danyeun01
3 ай бұрын
checking the highest only when a duplicate is detected shaves off a ~10 milliseconds in python albeit the code isnt as compact class Solution: def lengthOfLongestSubstring(self, s: str) -> int: highest = 0 l, r = 0, 0 chars = set() while r < len(s): if s[r] in chars: highest = max(highest, len(chars)) while s[r] in chars: chars.remove(s[l]) l += 1 chars.add(s[r]) r += 1 highest = max(highest, len(chars)) return highest
@ElijahManor
2 жыл бұрын
Great resource! I really like how you draw through the concept before coding.
@AlmightyWeick
5 ай бұрын
In the C# solution posted on the NeetCode website, it uses a HashSet to store the substring chars. Is there a reason for this? I assume it just stores the ASCII value, but is there a reason for using HashSet instead of HashSet (which seems more intuitive)?
@anirbansarkar6306
3 жыл бұрын
Thanks a lot. It was short, to the point and an easy to follow video. Really a great content to learn from.
@anirbansarkar6306
3 жыл бұрын
Although if possible, can you add time and space complexity explanations too? Like how have you calculated them. It would help us more.
@rams2478
2 жыл бұрын
Nice idea.. but i didnt quite understand how we get 0(n) with inner while loop...wouldn't it be 0(n2)?
@nikhil_a01
Жыл бұрын
Nested loops doesn't automatically mean O(N^2). It matters how many iterations there are in the loops and the time complexity of the operations in each iteration. The outer loop is growing the sliding window by iterating the r pointer through the entire string. It's O(N) because it goes through the whole string. The inner loop is shrinking the window by iterating the l pointer. But the l pointer never goes past the r pointer. It's basically lagging the r pointer. After all, the left side of the window can't overtake the right side. In the worst case the l pointer will also iterate through the entire string, which is O(N). Overall we get O(2N) which is equal to O(N). (And of course the set operations are O(1) so we are only doing O(1) work inside each loop iteration).
@manasisingh294
Ай бұрын
@@nikhil_a01 Thanks for explaining! :D
@darcash1738
9 ай бұрын
I had a different approach that seemed more intuitive and I don’t think it was any slower. I had the variables longest currentlongest, and the set. Enumerate through the string, if current val in the set, set currlongest to 0, clear the set(O(1)). If not, add 1 to current longest, add the Val to the set and check if greater than longest, if so setting equal to longest
@danielbartolini115
3 жыл бұрын
Very clever solution. But can anyone please tell me what the time complexity is? He has a while loop within a for loop so I'm not sure.
@kafychannel
Жыл бұрын
Thanks for your content, NeetCode. It is a great idea to draw the idea of solution thanks to this I coded this problem up on my own. Thank you so much!
@ap2s2000
2 жыл бұрын
You can change the way you compute the longest substring by just getting the length of the set
@shashikantdivekar7839
2 жыл бұрын
Very well described and helpful. Quality material. Thank you Sir.
@akinniyiakinyemi2737
8 ай бұрын
Great content as always. Just to point out, our space complexity for the set could be o(1) since there'll only ever be 26 chars if we're only dealing with the English alphabets
@ankitasharma4192
2 жыл бұрын
How is it O(n), as we are using a for and a while loop within ?
@salesrafael
2 жыл бұрын
The inner while loop is limited to 26 iterations (alphabet). So, worse case is O(n * 26) -> O(n) Here's an improved solution, though: leetcode.com/problems/longest-substring-without-repeating-characters/discuss/1889969/O(n)-faster-than-99.87-Sliding-Window-Optimized
@nikhil_a01
Жыл бұрын
That's completely wrong. It's got nothing to do with the size of the alphabet (which is not even 26 since this problem allows all English letters, digits, symbols and spaces). The reason it's O(N) is because the inner while loop across all its iterations is moving the l pointer through the whole string. It can never move the l pointer past the r pointer, and the r pointer iterates once through the entire string.
@Taziamoma
2 жыл бұрын
This is amazing :D Just one question. Why at the end (res = max(res, r- l + 1)), why are we adding 1 at the end?
@choleaoum1383
2 жыл бұрын
The 1 is because the for loop begins at 0 otherwise if you have a single item array the subset size would be 0 instead of 1.
@sarmadkhawaja2669
2 жыл бұрын
Why don't we use a list instead of set? When you said that set makes sure there is one of each element so does a list for this problem that is. Because you only add item at the right pointer to your list once you have removed it already using the while loop. I know appending to list or adding to set are both O(1). But what about removing form list vs set? Is removing from set more efficient and is that why a set is preferred? Asking cuz I was able to submit my solution with list instead of set and it still passed.
@shanejacob9054
2 жыл бұрын
Quick question. Why is the space complexity O(n)? The problem description states that s consists of English letters, digits, symbols and spaces. Since we're using a set which holds unique elements of S, the space complexity should be O(number of letters/digits/symbols/spaces), which is a finite number. Giving a space complexity of O(1)
@arturozenteno7524
2 жыл бұрын
Why is it r - l + 1? Why the + 1?
@Xeoncross
2 жыл бұрын
This answer doesn't seem correct. What if the string is "abb"? Assuming you get to [ab]b and are looking at the second "b". How will removing "a" (the first character) and adding "b" accomplish a correct result?
@valentinrafael9201
2 ай бұрын
Interesting, I ended up with this solution l = 0 r = 0 max_len = 0 while r < len(s): if s[r] not in set_string: set_string.add(s[r]) r+=1 max_len = max(max_len, r-l) else: set_string.remove(s[l]) l+=1 return max_len Because max_len is updated before the else statement, which increments l, it will not require the ugly "r-l+1". It will require the ugly "r-l" which is one less uglier.
@xaapt
Жыл бұрын
I watched this 3 times, still no idea how is it working :(
@juliomedina5446
6 ай бұрын
A slightly more elegant way (in my opinion!) would be to set res = max(res, charSet.size()). This way you would avoid the possibility of forgetting to add +1 and having a bug in your code during an interview!
@noahmader7325
2 жыл бұрын
I think space complexity would be O(1) because there are a finitie number of possible characters that could go into your hash/set despite how long the string is.
@edenrosales8214
2 жыл бұрын
I agree
@wol2231
11 ай бұрын
True. Great observation. For anyone wondering, the question has this constraint "s consists of English letters, digits, symbols and spaces." By definition, a set can't contain duplicates. so, the set will be finite.
@marisaliang3335
2 жыл бұрын
Thanks for the great video! A quick question on the space complexity of this problem: the leetcode details mention "s (input string) consists of English letters, digits, symbols and spaces." - would we then be able to consider this O(1) space complexity, as there is a finite max length for our charSet?
@arjunreddy2647
2 жыл бұрын
probably since it’s not a factor of string length
@seanshaw3493
3 ай бұрын
I am just wondering why the space complexity is O(n) but not O(1)? Since we are always keeping each distinguished char appearing only once, the max length of the HashSet is fixed and depands on how many distinguished chars we have in the specific language. Thus the space complexity should be O(some fixed number) -> O(1). Please enlight me if I got something wrong
@weiyihuang67
3 жыл бұрын
Short and clean solution! Easy to follow, thanks a lot!
@midicine2114
Жыл бұрын
Can also exchange the outer for loop with a while loop and manage the right pointer.
@venkatanishanthchaganty1697
11 ай бұрын
Just curious, Wouldn't the space be O(1) because even in the worst case, we know for a fact that the size of the set is not going to exceed 26 assuming every character is lowercase. Essentially, it is not scaling with input size and hence, we can say it has constant space complexity.
@akashvaidsingh
Жыл бұрын
we are running while loop inside for loop , so why the complexity is not N-square ?
@shengbinwang5892
2 жыл бұрын
I think the time complexity is large than O(n). Since there is a while loop inside of for loop. Is that correct?
@SaifAli-nt5sh
2 жыл бұрын
No. The while at Max can run only n times. And that will not be the case for every loop's iteration.
@Basta11
4 ай бұрын
The space complexity is not necessarily O(n). The number of characters is going to be finite even using the largest character set known to man. So its O(n) for when n is below the size of the character set and O(1) after that. Of course, if we've reached that point, then that is the max answer.
@siyahulhaq7062
8 ай бұрын
This approach is strikes on my mind when i see this video on my feed
@amadakram5722
Жыл бұрын
amazing explaination, but I came up with someting simpler I guess: def lengthOfLongestSubstring(self, s: str) -> int: if (len(s) == 0): return 0 maxS = 1 l = 0 r = 1 while r < len(s): substr = s[l:r] if (s[r] not in substr): r+=1 substr = s[l:r] maxS = max(len(substr), maxS) else: l+=1 return maxS
@harrywong4302
3 ай бұрын
You shouldn't update the left pointer by simply plus 1, instead do l += 1 + substr.index(s[r])
@efe3036
Жыл бұрын
Thanks for explaining this topics, you made it simple as a,b,c .I have been struggling on data structure, have never solve any problem on my own without making mistakes and searching for help. you made things easy. thank you.
@antoinenijhuis450
7 ай бұрын
Can someone explain me why the following code is slower runtime wise? It performs about 10 times slower than the solution provided by Neetcode. But I have no idea why. longestSS = 0 firstLettIndex = 0 collection = {} for i in range(len(s)): if s[i] not in collection: collection[s[i]] = i else: if len(collection) > longestSS: longestSS = len(collection) firstLettIndex = collection[s[i]] + 1 collection[s[i]] = i collection = {} for j in range(firstLettIndex, i+1): collection[s[j]] = j if len(collection) > longestSS: longestSS = len(collection) return longestSS
@davinanaya468
3 жыл бұрын
I love the way you explain, thanks for this explanation with real exercises
@momenwadood1342
2 жыл бұрын
why use a set if we remove duplicates before we add the next char?
@whitebaik
2 жыл бұрын
Thanks for the great solution. I'm a little rusty on the set and don't understand why the left pointer variable is declared outside the for-loop, instead of inside. What confuses me is that I thought the left pointer has to re-initialize to 0 every time we delete every duplicate and add the same character at the end of the set. For example, when we are at the iteration for the second "a" in string "abcab", the left pointer is incremented to 1 after removing the first 'a' and placing the second "a" at the end (which will result in "bca"). And then, if we want to access "b" in the next iteration, aren't we supposed to have left pointer at the 0th index instead of 1st?
@lronmate
2 жыл бұрын
It's key to realize that we're not actually removing any indices from the original string, s. When we run into a duplicate char, we remove the instance of that char from the SET, and move the left pointer ahead by 1 in the original STRING to represent the new window. We can't modify the original string, otherwise it would mess with using the for loop. edit: I know this was asked a few months before me answering it, but I figured I'd still comment in case anyone else has the same question.
@derrickaddo5531
3 жыл бұрын
It is it really O(n) if you are looping again to remove the chars from the set? Why not use an if statement instead of the while loop?
@gamrygamer5690
3 жыл бұрын
you have to keep on removing elements to make the elements unique in the substring
@arturlamaka1400
3 жыл бұрын
Agree. It should be O(n^2) as we have loop in loop, isn't it?
@ZubairKhan-tt8ev
3 жыл бұрын
@@arturlamaka1400 that while loop is capped to 26 as there are only 26 possible letter (entire alphabet) that can constitute the set. so worst case is O(n * 26) -> O(n)
@nikhil_a01
Жыл бұрын
It's got nothing to do with the size of the alphabet (which is not even 26 since this problem allows all English letters, digits, symbols and spaces). The reason it's O(N) is because the inner while loop across all its iterations is moving the l pointer through the whole string. It can never move the l pointer past the r pointer, and the r pointer iterates once through the entire string.
@mertzorlu386
2 жыл бұрын
guys print(charSet) in while loop after remove and print(charSet) after .add also add a print('after addition) and see the transition making lot of sense!
@Syedaxox
3 жыл бұрын
This was very well-explained. The only thing I don't understand is why you would use a while loop, rather than an if statement?
@Syedaxox
3 жыл бұрын
Figured it out a second after asking lol. Nvm. Thank you for the video!
@mitramir5182
Жыл бұрын
@@Syedaxox can you say why he's using a while? We only have one repetition of every character in a set. It's not a list.
@nikhil_a01
Жыл бұрын
@@mitramir5182 The left side of the window needs to shrink until there are no duplicates in the window. The window is defined by the l and r pointers. We calculate the max length based on those pointers so we can't have a substring that has duplicates.The set is just a convenient way to quickly check for duplicates. Let's say our input is "pwwkew" and right now our charSet contains {p, w}. When we take the second 'w' we see that we have a duplicate because it's already in the set. Now let's say we only remove s[l] and increment l once instead of using a while loop. We just removed the 'p' and incremented l to 1. Then we add the second 'w' to charSet. It's true that our charSet is only {w} because it's a set. But our window is "ww" which has a duplicate. This isn't valid, so we're not going to calculate the correct max length later on. What we needed to do was keep removing from our window until we get rid of that first 'w', which is why we used a while loop.
@Mpjadhav1144
2 жыл бұрын
i think 12th line should be res=max(res,len(charSet)) since res= max(res, r-l+1) is giving me the length of original string
@chookingvid
2 жыл бұрын
Instead of a set, I used an array of length 128 to keep track of the characters via their ASCII value as index. This has terrible performance in Python (slower than half of all submissions), but the performance in C++ and Rust is great. I got 0ms 100% faster than all submissions for both of those languages. I realize that the space complexity is not good, but I was trying to see if I could get it faster than a set. Also, I am aware that this would not work at all for unicode.
@nachiket9857
Жыл бұрын
I found using a queue easier for internalising this problem better: class Solution: def lengthOfLongestSubstring(self, s: str) -> int: l = 0 lst = collections.deque() res = 0 for r in range(len(s)): while s[r] in lst: lst.popleft() l += 1 lst.append(s[r]) res = max(res, r - l + 1) return res
@ianokay
11 ай бұрын
What wasn't immediately intuitive to me is that we can stop when the right pointer hits the end and not care about the left doing any more things (shortening I guess).
@jaidenlee7394
4 ай бұрын
Wouldn't it be more efficient to use a hashmap/dictionary instead of a set, and store the last seen occurrence of each character. By doing this, you can adjust the left pointer in O(1) since you can just move it past the index of the last occurrence. This makes it so that you never have to go back to an already visited index, unlike using a set which might require you to revisit all previously visited indices.
@SmoothCode
3 жыл бұрын
How does the variable l act as a pointer when it is initialized as 0? What are we accomplishing by incrementing l by 1 each time we find a duplicate character?
@MichaelShingo
Жыл бұрын
When you find a duplicate character, it means that you've found the maximum string length given that L value. So you increment L by 1 until that duplicate is gone. Now you have another L value, from which you can start increasing the window size, to potentially find a larger string length.
@beransantur7611
Ай бұрын
I didn't quite understand why the worst time complexity is o(n) since we could potentially check the whole input size twice imagine an input such this. "abcddcbaabcd " don't we check the whole thing twice?
@floydian25
Жыл бұрын
so why use set? Cant we use Stack instead? do we require the ability if set that doesn't store duplicates?
@Exploshi
6 ай бұрын
this is the solution that i came up with intuitively but why is it so slow? is there a faster solution?
@ankitsablok952
2 жыл бұрын
I had the same intuition but then I got hung up on making use of a TreeMap instead of a Set and then kinda lost the track of how to remove the element from the collection. But I guess I was very close to the same solution. Watching the first couple minutes of the video I was able to come up with the code myself. Nice explanation!
@martinlacsamana7534
Жыл бұрын
Also used a hashmap instead and was confused with this
@TofuCate
2 жыл бұрын
can't we just do res = max(res, len(charSet)) instead
@ash1ash199
2 жыл бұрын
I get a wrong answer on leetcode any idea why?
@henrmota
Жыл бұрын
Thanks for this videos I am learning rust while I implement this algorithms :).
@sachins6196
2 жыл бұрын
Beautifully done
@ethannguyen6240
7 ай бұрын
Wow. what a clean explanation. Thanks!
@LandoKalrissian
Жыл бұрын
@NeetCode The space complexity is O(1), not O(n), because the description says "s consists of English letters, digits, symbols and spaces.", which means the size of the set of different characters is fixed (less than 127, size of the ASCII table).
@tsw781
2 жыл бұрын
This was a great explanation for this problem. Thank you.
@iayushbhartiya
2 жыл бұрын
what if I use 'if' instead of while?
@geld5220
Жыл бұрын
right-left + 1 that is confusing me but I understood now that The expression right - left + 1 calculates the length of the current substring by subtracting the left pointer left from the right pointer right and adding 1 (because the length of a substring is the difference between the indices plus 1).
@geld5220
Жыл бұрын
believe me it made sense when i was saying it but reading it again just confused the heck out of me
@musayo9482
3 жыл бұрын
It makes it so much clearer! Thanks!
@millenialmusings8451
2 жыл бұрын
At 3:18 why do we need to remove 'a' if it's not repeating?
@tavinsingh1
8 күн бұрын
Can someone explain why the space complexity wouldn't be O(1) since the maximum number of characters that could ever be in the set is 26(assuming we have a string of all unique letters)
@saideep7510
2 күн бұрын
Firstly the characters in set could include English letters, digits, symbols and spaces so thats more than 26 characters. Secondly we should always consider the complexity as the worst case scenario. So even if in this case lets consider if the input string had 26 unique characters (the length of string is n (n being the total number of characters in the string)) then the set would include all those 26 characters. So the size of the set would also be n. Hence the space complexity is o(n).
@SouthernHadoken
2 жыл бұрын
How are you removing elements from the left side when a set is not ordered. ??
@qf4364
2 жыл бұрын
I didn’t get the point why we have a while loop here, it just execute once for each r , right¿
@patilashish
2 жыл бұрын
Hey @NeetCode the while statement could result in O(n) operation for last char in a no duplicate string. Hence the time complexity would be O(n^2). A constant time operation N times is O(N) operation.
@andresivanmonterocassab5486
2 жыл бұрын
Hi, yes is a bit tricky when you have a while loop inside a for loop, but what helps me is to try to see how many times you will visit each character, you are right that the worst case for the while statement would be O(n) but this could only happen one time (the worst case, all the other cases you will only add and pop a few chars), so in the end you will visit each element once inside this while loop and you will visit each element once in the for loop so the time complexity is O(2n) which converges to O(n)
@rekcahY
Жыл бұрын
@@andresivanmonterocassab5486 nice, I was scratching my head on this because it totally looked like O(n*2) to me... haha
@pavannettam8968
2 жыл бұрын
how can membership of a set happen in constant time? if not then the time complexity of your code will be O(n^2)
@nikhil_a01
Жыл бұрын
It's a hash set. Similar to a hash map but it only has keys and no values. So it is O(1) lookup.
@JamesBond-mq7pd
8 ай бұрын
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: array = [] max_size = 0 for i in range(len(s)): while s[i] in array: array.pop(0) array.append(s[i]) max_size = max(max_size, len(array)) return max_size
@tachyon7777
6 ай бұрын
You don't need the inner while loop or the .remove operations.
@pradeethbathina3474
2 жыл бұрын
Hey @NeetCode, I think it should be if clause instead of while.... because now you got complexity as O(n^2)
@nikhil_a01
Жыл бұрын
It's not O(N^2). There are already a couple of comments on this video explaining why it's O(N). And you can't just change the while loop to an if statement. The algorithm won't return the correct results. You have to shrink your window until there are no more duplicates, which you can't do with just an if statement.
@erikm9768
2 жыл бұрын
Is there a difference between removing s[l] and just removing by index l?
@admercs
2 жыл бұрын
Yes. A set generally re-orders the objects, so the index varies.
@manasisingh294
Ай бұрын
@@admercs Thank you for the explanation! :D
@nikhilkm1892
3 жыл бұрын
Why would you use a while loop and not just an if condition for removing character from charSet? That's a bit confusing. I would expect only one occurrence of s[r] in charSet as it is a set.
@nikhilkm1892
3 жыл бұрын
Chuck that. I think I got it. You are removing all characters till the character where you found the duplicate as any other substring between l and r would be smaller than what we have already found. Is that right?
Пікірлер: 323