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!
@@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
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
@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
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
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
@@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) .
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?
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.
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
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).
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!
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.
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.
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%
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 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
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.
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
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
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))
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.
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.
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.
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.
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
@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.
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.
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!
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
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.
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.
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.
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!
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).
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.
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
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
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
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.
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.
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!
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!
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?
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.
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)?
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
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
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?
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
@@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.
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)
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).
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?
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.
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.
Check Out This one: class Solution: def lengthOfLongestSubstring(self, s: str) -> int: temp = ans = "" for i in s: if i in temp: temp = temp[temp.index(i) + 1:] temp += i ans = temp if len(temp) > len(ans) else ans return len(ans)
My solution a bit simple approach a="abcabcbb" b=[] for v in range(len(a)): for i in range(len(a[v:])): if len(a[v:][:i+1])==len(set(a[v:][:i+1])): b.append(a[v:][:i+1]) print(len(max(b,key=len)))
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.
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
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?
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.
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)
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?
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.
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).
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.
Hi, many thanks! however, there's probably a more optimal solution, as this approach beats 51% only of LeetCode Ruby users, and beats less in terms of memory :)
@@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)
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.
@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).
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
🚀 neetcode.io/ - A better way to prepare for Coding Interviews
Why did you pick sliding window approach.I didnt understand the thinking process of this algo selection
well, great video, but i did not unerstand the last move - "r-l+1", could u explain
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!
@@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
@@rajakrishna Thanks for the details.
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
Is that true? LC errors out when I call charSet.size()
@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
@@brickndick If you're doing LC in Python, it should be len(charSet)
This is good because i was wondering why we created a set id we are not using it in any determining operation
That’s more understandable, r - l + 1 is confusing.
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
Thank you! Quite a great summary, especially important for me was your note about last pitfall.
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
For that matter we could of used a dictionary, because look up in a dictionary is 0(1)
@@zionroar9066 but it takes more space than a set bc the keys. Always better to optimize time AND space complexity
@@user-us4mc7ej3c they are the same in terms of "space complexity".... O(N).
@@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) .
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?
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.
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
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).
You're the best. Got selected at Amazon because of your teaching.
One of the cleanest solutions i have come across, thanks!!
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!
The debugger in leetcode does the same or is vscode better?
@@chilo7272 well, the vscode debugger is free
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.
alternatively you can use:
res = max(res, len(found))
I think that maybe a bit cleaner and intuitive for some.
what is "found" here?
@@ahmadyasser9317 charSet
thanks that makes more sense to me
Less space-time efficient though.
Appreciate the content! It might be useful at the end to do a quick summary and run through just to cement the idea. Thanks!
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.
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%
Bruuuh i really got stuck for hours on this problem set and almost got 50 lines and this dude did it in 13 lines 😩😩😩😩😩
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.
Can you please provide the code using hashmap?
@@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
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.
Space complexity should be o(1) as there are limited number of characters in the alphabet,
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
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
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
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.
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.
This solution does not work for test case 'pwwkew'. Any updates on why it doesn't pass.
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.
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.
Yeah, I agree a hashmap is probably better in this case. That said, the worst-case time complexity should stay the same.
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
@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.
@@randomkoolstuff hi! please why did you set the max length to be 1 initially in your code?
it isnt better
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"?
while will run until the condition becomes false, if just checks once and exits
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.
@@MIDNightPT4 You saved my brain, that's exactly what I was trying to figure it out
I did hashset of chars+queue+sliding window technique, got 12 ms for C++(faster than 93%). Anyway clean and neat solution bro, congrats!
one of the best algo/ds interview prep channels out there!!!!
Thanks a lot. It was short, to the point and an easy to follow video. Really a great content to learn from.
Although if possible, can you add time and space complexity explanations too? Like how have you calculated them. It would help us more.
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.
Very well described and helpful. Quality material. Thank you Sir.
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!
the #2 while is not needed
charSet = set()
l = 0
c=0
big = 0
while(c
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
I watched this 3 times, still no idea how is it working :(
You can change the way you compute the longest substring by just getting the length of the set
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.
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.
I agree
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.
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!
Can also exchange the outer for loop with a while loop and manage the right pointer.
Nice idea.. but i didnt quite understand how we get 0(n) with inner while loop...wouldn't it be 0(n2)?
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).
@@nikhil_a01 Thanks for explaining! :D
Great resource! I really like how you draw through the concept before coding.
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.
This approach is strikes on my mind when i see this video on my feed
Short and clean solution! Easy to follow, thanks a lot!
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
You shouldn't update the left pointer by simply plus 1, instead do l += 1 + substr.index(s[r])
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
umm don't u think this will be O(N^2) since we have a nested loop here ?
How is it O(n), as we are using a for and a while loop within
?
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
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.
I love the way you explain, thanks for this explanation with real exercises
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.
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!
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!
Also used a hashmap instead and was confused with this
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?
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.
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)?
Thanks for this videos I am learning rust while I implement this algorithms :).
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
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
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
Wow. what a clean explanation. Thanks!
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?
probably since it’s not a factor of string length
This was a great explanation for this problem. Thank you.
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
Beautifully done
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?
Figured it out a second after asking lol. Nvm. Thank you for the video!
@@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.
@@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.
I think the time complexity is large than O(n). Since there is a while loop inside of for loop. Is that correct?
No. The while at Max can run only n times. And that will not be the case for every loop's iteration.
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)
It makes it so much clearer! Thanks!
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).
believe me it made sense when i was saying it but reading it again just confused the heck out of me
we are running while loop inside for loop , so why the complexity is not N-square ?
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?
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.
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?
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.
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.
Check Out This one:
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
temp = ans = ""
for i in s:
if i in temp:
temp = temp[temp.index(i) + 1:]
temp += i
ans = temp if len(temp) > len(ans) else ans
return len(ans)
My solution a bit simple approach
a="abcabcbb"
b=[]
for v in range(len(a)):
for i in range(len(a[v:])):
if len(a[v:][:i+1])==len(set(a[v:][:i+1])):
b.append(a[v:][:i+1])
print(len(max(b,key=len)))
Hey @NeetCode, I think it should be if clause instead of while.... because now you got complexity as O(n^2)
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.
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
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?
why use a set if we remove duplicates before we add the next char?
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.
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)
@@andresivanmonterocassab5486 nice, I was scratching my head on this because it totally looked like O(n*2) to me... haha
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?
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.
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).
one of the best explanation
Thanks a lot man.. easy understable solution
It's a very beautiful solution.
Great approach!
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.
Thank you for doing this video!
Hi, many thanks! however, there's probably a more optimal solution, as this approach beats 51% only of LeetCode Ruby users, and beats less in terms of memory :)
Thank you for your solution!
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?
you have to keep on removing elements to make the elements unique in the substring
Agree. It should be O(n^2) as we have loop in loop, isn't it?
@@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)
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.
wow so concise
@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).
Why is it r - l + 1? Why the + 1?
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
Best explanations ever!
You don't need the inner while loop or the .remove operations.
Thanks for making it dude
Solution is O(2n), may implemenet in O(n). I mean could be optimized.
so why use set? Cant we use Stack instead? do we require the ability if set that doesn't store duplicates?