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
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?
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
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
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%
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))
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.
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
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.
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.
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!
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.
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
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.
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.
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
@@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!
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)?
Explanation of res = max(res, r-l+1) Suppose we're processing the string "abcabcbb" and we're currently at the substring "abc". l is the left boundary of the sliding window, which is 0 (index of 'a'). r is the right boundary of the sliding window, which is 2 (index of 'c'). r-l+1 calculates the length of the current substring, which is 2-0+1 = 3. the answer is -> '3'
Since everything up to (but not including) r is known-visited, we don't need the loop, do we -- just... res = 1 l = 0 charSet = set(s[l]) for r in range(1,len(s)): if s[r] in charSet: res = max(res, r-l) charSet = set(s[r]) l = r else: charSet.add(s[r]) We already know that everything between l and r has been visited by r, just set the set to r's current char and jump l to r's index. This seems optimal.
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
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?
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)
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!
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
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.
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.
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!
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.
@@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.
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?
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.
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
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)
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).
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
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
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.
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.
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.
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).
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 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!
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?
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).
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)
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.
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)))
@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).
List is O(N) to remove an element, and O(N) to check if an element exists. A set is O(1) for both of those operations. So you don't 'require' a set, but your solution will be O(N^2) if you use a list instead of a set, which is not a very good solution.
def lengthOfLongestSubstring(s: str) -> int: “””Clean version with clear pointer behaviour.””” st = set() l = 0 r = 0 res = 0 while r < len(s): if s[r] not in st: st.add(s[r]) res = max(res, r-l+1) r += 1 else: st.remove(s[l]) l += 1 return res
longest = 1 curr = 1 i = 0 j = 1 if len(s) == 0: return 0 myhash = {s[0]: 0} while j < len(s): if s[j] not in myhash: myhash[s[j]] = 0 curr += 1 longest = max(longest, curr) j += 1 else: curr = 1 i += 1 j = i+1 myhash = {s[i]: 0} return longest I did this using a hashmap Can someone explain me the time complexity of the above code?
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.
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)
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).
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 :)
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.
🚀 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.
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?
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.
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.
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're the best. Got selected at Amazon because of your teaching.
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!
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.
One of the cleanest solutions i have come across, thanks!!
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.
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.
Appreciate the content! It might be useful at the end to do a quick summary and run through just to cement the idea. Thanks!
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%
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
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.
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
Bruuuh i really got stuck for hours on this problem set and almost got 50 lines and this dude did it in 13 lines 😩😩😩😩😩
I did hashset of chars+queue+sliding window technique, got 12 ms for C++(faster than 93%). Anyway clean and neat solution bro, congrats!
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
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.
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
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.
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])
Very well described and helpful. Quality material. Thank you Sir.
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
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.
one of the best algo/ds interview prep channels out there!!!!
Can also exchange the outer for loop with a while loop and manage the right pointer.
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.
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
@@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!
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)?
Explanation of res = max(res, r-l+1)
Suppose we're processing the string "abcabcbb" and we're currently at the substring "abc".
l is the left boundary of the sliding window, which is 0 (index of 'a').
r is the right boundary of the sliding window, which is 2 (index of 'c').
r-l+1 calculates the length of the current substring, which is 2-0+1 = 3.
the answer is -> '3'
You can change the way you compute the longest substring by just getting the length of the set
Great resource! I really like how you draw through the concept before coding.
Since everything up to (but not including) r is known-visited, we don't need the loop, do we -- just...
res = 1
l = 0
charSet = set(s[l])
for r in range(1,len(s)):
if s[r] in charSet:
res = max(res, r-l)
charSet = set(s[r])
l = r
else:
charSet.add(s[r])
We already know that everything between l and r has been visited by r, just set the set to r's current char and jump l to r's index.
This seems optimal.
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
This approach is strikes on my mind when i see this video on my feed
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?
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)
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!
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
Short and clean solution! Easy to follow, thanks a lot!
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 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.
I love the way you explain, thanks for this explanation with real exercises
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!
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.
Thanks for this videos I am learning rust while I implement this algorithms :).
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.
umm don't u think this will be O(N^2) since we have a nested loop here ?
Wow. what a clean explanation. Thanks!
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.
Space complexity should be o(1) as there are limited number of characters in the alphabet,
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
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.
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
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)
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
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
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
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.
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.
Beautifully done
wow so concise
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.
This was a great explanation for this problem. Thank you.
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.
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
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.
one of the best explanation
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.
Great approach!
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
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?
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).
It's a very beautiful solution.
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
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.
we are running while loop inside for loop , so why the complexity is not N-square ?
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
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 makes it so much clearer! Thanks!
I watched this 3 times, still no idea how is it working :(
@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).
Thanks a lot man.. easy understable solution
We do not require set to solve this. This can also be handled with List. Use List instead of Set, and append instead of add.
Set doesn't allow duplicate values, thats why its handy to use.
List is O(N) to remove an element, and O(N) to check if an element exists. A set is O(1) for both of those operations.
So you don't 'require' a set, but your solution will be O(N^2) if you use a list instead of a set, which is not a very good solution.
def lengthOfLongestSubstring(s: str) -> int:
“””Clean version with clear pointer behaviour.”””
st = set()
l = 0
r = 0
res = 0
while r < len(s):
if s[r] not in st:
st.add(s[r])
res = max(res, r-l+1)
r += 1
else:
st.remove(s[l])
l += 1
return res
def lengthOfLongestSubstring(s):
longest = 1
curr = 1
i = 0
j = 1
if len(s) == 0:
return 0
myhash = {s[0]: 0}
while j < len(s):
if s[j] not in myhash:
myhash[s[j]] = 0
curr += 1
longest = max(longest, curr)
j += 1
else:
curr = 1
i += 1
j = i+1
myhash = {s[i]: 0}
return longest
I did this using a hashmap
Can someone explain me the time complexity of the above code?
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.
You don't need the inner while loop or the .remove operations.
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)
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).
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 :)
so why use set? Cant we use Stack instead? do we require the ability if set that doesn't store duplicates?
this is the solution that i came up with intuitively but why is it so slow? is there a faster solution?
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.
Best explanations ever!
Thank you for doing this video!
Thanks for making it dude