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
@@tomerharari633 it's the same. check how HashSet is implemented internally, it's backed by HashMap. the only difference with add and put(key, value), but you can do Contains in both cases, for map it's containsKey, containsValue, when for Set it's contains. it's eventually your choice.
you just taught a 46 year old, non CS grad, how to handle this problem. thank you. This is more to the point than the solution in leetcode. Keep up the good work.
Crystal clear help man, appreciate it so much I was struggling with this one, just when I thought I had it each time there would be some test failing on submission. You did great explaining exactly what was happening so hats off to you my friend!
Sir, I want to let you know, you are the best! I have been stuck on this question for few hours now, going through solutions on LeetCode and trying to make sense. Now, I watched this video and everything makes sense.
Instead of incrementing "a_pointer" by 1 , we actually have to set it to the index at which we last saw the character at "b_pointer". To store this information, we need to use a Map (instead of a Set)
This will still work because a_pointer was never incremented if duplicate was found. So this will always give you the correct answer. I'll recommend working this through a example string.
@@kunalnarang1912 I had to tweak this solution a bit to make it work as it didn't seem to work for string "pwwkew" class Solution { public int lengthOfLongestSubstring(String s) { int maxLength = 0; int aPointer = 0; int bPointer = 0; Set visited = new HashSet(); while(bPointer < s.length()){ if(!visited.contains(s.charAt(bPointer))){ visited.add(s.charAt(bPointer)); bPointer++; maxLength = Math.max(maxLength, visited.size()); } else { while(s.charAt(aPointer) != s.charAt(bPointer)){ visited.remove(s.charAt(aPointer)); aPointer++; } visited.remove(s.charAt(aPointer)); aPointer++; } } return maxLength; } }
suppose string is "bacad", now when b pointer is at index 3 (when a comes 2nd time), this algorithm will remove b from the sliding window leaving string a ""aca" in it and still it has repeating character a. Please correct me if I am wrong.
The remaining string will be "aca", that's right. Keep going through the while-loop though. On the next iteration of the while loop, b_pointer will still be at the second "a". Since "a" is still in the hash_set, the code will go to the else block, remove "a" from the hash_set, and increment a_pointer. Then, you're left with "ca". Notice that b_pointer is still at "a". So in the next iteration, it will add "a" to the hash_set again since we're still at that char and we've just removed the other "a".
While trying the solution on my own, I stumbled across how to eliminate duplicate characters from a string. So, now, thanks to your video I can do both. :)
Question, if a duplicate occurs is it always the character at a_pointer that can be duplicate. Eg Say if I have "abcdb", my a_pointer is at 0 and b_pointer is checking window. After 'd', it encounters 'b' however popping character at a_pointer(which is 'a') results 'bcdb' which still has duplicates..?? If duplicate occurs, is it always same character at a_pointer which can be duplicate..??
I see your point -- the fact is Nick didn't explain this part clear enough. Beware of the fact that b_pointer will not move unless the duplicate is cleared. So you can see it as a continuous loop until the duplicate at b_pointer is found and removed from the substring, then the b_pointer will go on incrementing. Otherwise, a_pointer is just going to continue moving right while b_pointer sits still, letting the substring shrink every iteration.
@@ianpan0102 Make sense . Thanks for explaining. Until whatever duplicate is removed only "else part" is executed shrinking the hash . Finally after duplicate is removed, b_pointer will progress again.
I'm watching your videos because i just graduated and I'm preparing for these tough ass interviews. Your videos are nice and helpful. I wish I could do these problems by myself lmfao. You got any tips on how to get better at ACTUALLY coding these problems? I feel like I try and I don't get it and I tend to get frustrated and give up haha
...also after you've completed a few, you'll have a basic understanding that most of the questions following the same principles which allow you to solve similar questions with the same or slightly different solutions.
@@NickWhite what if I keep looking at solutions then? I sometimes feel that if I have to lookup solution, it is kinda cheating and not the natural process of learning.
Take "pww" for example. If the b_pointer encounters w, at index 2, we will remove "p" from the set. At this time, the set is [w], and b_pointer still points to the "w" at index 2. After removing "p", since the set still contains the value of b_pointer, we will again removing "w" from the set. Now the set becomes []. The two pointers both point to the index of 2, and we add the w at index 2 to the set.
I might be missing something but suppose you had something like : "abbcd" how would this system detect that there is a repeat. Because it would just see that there is no a repeat and it would just go through?
Would you say time complexity is O(n) and space complexity is O(1) constant space, because no matter how long the input string can be, at any given time the worst case extra space we're dealing with in the hashset is 26 characters?
One improvement I would suggest, in the else-clause when the character is found in the set, instead of removing it simply increment both a_pointer and b_pointer. You're going to end up writing the value back in the set next loop iteration anyways, so you can save yourself a cycle.
When we get to a character that is already in the set, how do we know that the last time we seen that character it was at the index of a_pointer? I am a bit confused as to how we know that always removing the character at a_pointer from the set will always be the duplicate character? Like how do we know the duplicate character is not any other character between a_pointer and b_pointer?
Nice. Thank you. You can also add a while loop on your else statement to make it a little faster. while (hash_set.contains(s.charAt(b_pointer))) { hash_set.remove(s.charAt(a_pointer)); a_pointer++; }
Thank you for the video, I wish that you ran the code to give it a test and also see that there a miniscule typo in it. But, that does not change the fact that the solution is straightforward.
This is a very straightfoward solution and approach to the problems. Could anyone verify with me the time complexity is O(N) and space complexity is O(N) because of the size of HashSet?
Excellent explanation.. Liked it. You don't have to worry about the errors, it happens with everyone. You are making us understand and explaining the alogorithm so well - that's the most considerable and fabulous thing.
Guys, I understand why we remove character in else clause but why we remove character in a_pointer. I was expecting to remove b_pointer since we check if character in b_position is present in Hashset? What if string is dbcabcbb? when you found b is already in Hashset you'll have to remove d at the beginning. We should've remove b, right?
Say the given string is "abbb" According to the code in the video - a_pointer and b_pointer = 0; first - 'a' gets into the hashset, next - 'b' gets in. So far OK. (a_pointer is still 0 and b_pointer goes to 2) Then, the second 'b' arrives - now 'b' already exists in the set, so it goes to the else part and removes s.chartAt(a_pointer) which is 'a'???? It should be removing 'b'!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! Though the max variable helps get the answer, is the procedure right?
Why can't we solve it with only one pointer and a set? One pointer iterates through the array meanwhile adds the chars into a unique set. Then whenever we see the same char (if it can not be added into unique set) we get the max length and clean the set. Then continue until the end of the array.
Why remove @a_pointer? Is it because we have to find the last occurence of current char in hash to deduce length? Also we can do this max = ((b_pointer- a_pointer)>max)? (b_pointer - a_pointer):max; for max isn't it?
Solution is good but what if we replace string S="abcabcbb" to S = "abcbacbb" then the above solution will remove 'a' instead of 'b' because of a_pointer. string s = "abcbacbb"; if (s.Length == 0) return; int result = 0; int[] cache = new int[256]; for (int i = 0, j = 0; i < s.Length; i++) { j = (cache[s[i]] > 0) ? Math.Max(j, cache[s[i]]) : j; cache[s[i]] = i + 1; result = Math.Max(result, i - j + 1); }
I was thinking the same but then I saw "b_pointer is only increased while adding to hash set" otherwise "it will keep going to else statement and carry on deleting and increasing a_pointer". Also to maintain insertion order LinkedHashSet is used which is missing.🙂
I think there is something wrong with your solution. If there is a string "pwwkew", when your left pointer points to the "p" and the right pointer point to the second w, the HashSet will remove "w". However, at this time, your left pointer is pointing the first " w " and the right pointer is pointing the second" w ", and the letter "w" is not in the HashSet.
So why are you removing "a" pointer when hashset contains element pointed by "b" pointer? Meaning, if i deal with "abcbc" when the end is at second"b" your algorithm removes a just wanted to understand why
What I think happens, in the case of "abcbc" where the duplicate character is not the first character, each loop, an element will be removed until the duplicate character is removed. So yes the "a" will be removed when we have the second "b" but then on the next loop, the first "b" will be removed as well so then our hash set will just be "c" at which point it will try to add the second "b" again and will be successful since the first "b" was removed.
I naturally gravitated towards the same solution, but I think left pointer and right pointer runs over the same element twice which makes this solution not the most optimized one. It is still an O(2n) solution which is not bad but it could be better.
Since we are not incrementing b_pointer in case of a repeated char, the next couple of iterations will use the same repeated char and move the a_pointer to the next index after the first index of the repeated char.
This is completely wrong. Advances the left index by 1, assuming that the repeated character is always there, but it might be anywhere in the substring.
It isn't explained, but since the right index isn't incremented the loop checks the set again for the duplicate. The idea is that it shrinks the window from the left until the duplicate is removed and the current letter that triggered the duplicate found condition can be inserted into the set. This gives it a similar operation to using a map to index each letter and then shrink the window to the index following a duplicates last seen index. The difference being with a map you can immediately shrink the window to the new size rather than decrement the window until you find the new size.
Explained well. But the string we are getting at the end in hashset is not the expected string always. As we are returning the max size of the substring which is still intact because of the the Math() (max) operation.
There are different tricks in Python that aren’t exactly similar to Java code, what you can do is look at this exact question on leetcode then look in the discussion comments and look at the python solutions people have come up with. That should help
Eh, Idk, maybe just write it in python following the same logic line by line? Following works, everybody. def lengthOfLongestSubstring(self, s: str) -> int: if (len(s) == 0): return 0 left = 0 right = 0 ls = list(s) longest_set = set() longest = 0 while right < len(ls): if ls[right] in longest_set: # If duplicate seen, two type of "duplicate seen" longest_set.remove(ls[left]) # very important, remove the left pointer element left += 1 else: # ls[i] not in longest_map, aka see a new character non-duplicate longest_set.add(ls[right]) longest = max(longest, len(longest_set)) right += 1 return longest
public static int lengthOfSubString(String input){ List subString = new ArrayList(); Arrays.asList(input.split("")).forEach(val -> { if (!subString.contains(val)) subString.add(val); }); return subString.size(); }
This was excellent! Just one question, wouldn't you want to remove the charAt(b_pointer) from the HashSet instead of a_pointer? For instance, for a string abcc, when you see the second 'c', you'd actually be removing 'a', correct?
He doesn't explain it, and there are other videos that do, but since it removes a and doesn't increment the b pointer it would check again and then remove b, and then c until only that 2nd c remains and the substring checks continue. The idea is that the window grows to the right (bpointer) as long as characters are unseen and shrinks from the left (apointer) until the duplicate that triggered the shrink gets removed. Leaving you to find the longest substring based on the size of the window.
in the example of pwwkew first iteration will be : storing p and then storing w and then removing w so I increment , so now j will be indexed to W it will add it to the set , now we have w k e but then we have w so we gonna remove it from the set , finally we gonna get only ke which is not correct
You could move the a_pointer to the index after the first repeating character, instead of traversing the sequence, that would skip a lot of iterations!
First we have "pw" in the Set and max is 2 at this point, then we see another "w", we remove p and increment a pointer, set contains only w we add k, set is "wk" we add e, set is "wke" and max will become 3 we see "w", remove the "w" and max is still 3
This got me stuck too. He didn't explain the "pwwkew" part. You need to run debugger (or by hand) to walk it through to kinda grasp it. Apparently the same logic works for pwwkew too.
I have a question about LeetCode in general... Are people expected to derive these out by themselves, coming up with the sliding door idea from nothing, or do most people learn how to implement it through a video like this?
Doesn't work for "pwwkew", solution doesn't ensure that the hash set contains a substring. It will keep 'p' in the hashset unti the next p, but if there isn't one, your final max will be 4 as you can have a hashset p,w,k,e when it should hbe w,k,e (or k,e,w). Since youtube deleted the dislike count, now a ton of newbies will think this is the correct solution and fail their interviews.
Bro , solution is correct.when 'p' comes it adds it in set incrementing "b"(b at 1),when next character 'w' comes it also added in set ,incrementing the "b"(b at 2) ,max value =2,now when the second 'w' comes it removes the character at "a"(0) position which is 'p' incrementing "a"(a at 1) and set size is now=1 and when we iterate again at b index it is still 'w' so remove 'w' from set now the set size is zero,when we iterate again as 'w' is not in set it added in set incrementing b. likewise the code runs.
Yes there are more things to do in else block for it it work. I was doing it in PHP so slightly different but in the else block I had to cut out the string from the found letter until the end plus add the found letter to the end of the string and then it worked. The basics of the examples and the way of thinking are good though in the video.
It's 5: "qrsvb" is the longest substring. If you add the 's' after 'b', you get a repeating character. All other substrings without repeating chars are shorter than this one.
![Lp. Сердце Вселенной #60 РОЖДЕНИЕ ЛОЛОЛОШКИ [Финал] • Майнкрафт](http://i.ytimg.com/vi/YoR0pAV9FVQ/mqdefault.jpg)
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
I see u going on every video and commenting out the same thing. 😂
Anyway, really appreciate ur point.
@@tahaansari5621 it's actually good because not everyone will watch his each and every video
It is very informative comment since choosing what data structure will be used is the most important one when solving the tests.
Thanks a bunch
What's wrong with a hashmap though? because checking if hashmap contains a key is also O(1) isn't it?
@@tomerharari633 it's the same. check how HashSet is implemented internally, it's backed by HashMap. the only difference with add and put(key, value), but you can do Contains in both cases, for map it's containsKey, containsValue, when for Set it's contains. it's eventually your choice.
you just taught a 46 year old, non CS grad, how to handle this problem.
thank you.
This is more to the point than the solution in leetcode.
Keep up the good work.
Thank you man... I was smashing my head over this problem for more than 3 hours
you are single-handedly carrying my leetcode journey, thank you so much!
Crystal clear help man, appreciate it so much I was struggling with this one, just when I thought I had it each time there would be some test failing on submission. You did great explaining exactly what was happening so hats off to you my friend!
This code is obviously much readable than the official LeetCode solution, great job dude!
What if we had abcc? This would pop out a and have bcc in the hash set? Very confused why you'd pop from the beginning
the max stores the maximum of hashset size and current max..also note we have to check each and every substring.
Sir, I want to let you know, you are the best! I have been stuck on this question for few hours now, going through solutions on LeetCode and trying to make sense. Now, I watched this video and everything makes sense.
Instead of incrementing "a_pointer" by 1 , we actually have to set it to the index at which we last saw the character at "b_pointer". To store this information, we need to use a Map (instead of a Set)
Ditto, this will fail for "aabaab!bb" unless this fix is applied :)
This will still work because a_pointer was never incremented if duplicate was found. So this will always give you the correct answer. I'll recommend working this through a example string.
I'm actually trying with map. can you please share code?
@@kunalnarang1912 I had to tweak this solution a bit to make it work as it didn't seem to work for string "pwwkew"
class Solution {
public int lengthOfLongestSubstring(String s) {
int maxLength = 0;
int aPointer = 0;
int bPointer = 0;
Set visited = new HashSet();
while(bPointer < s.length()){
if(!visited.contains(s.charAt(bPointer))){
visited.add(s.charAt(bPointer));
bPointer++;
maxLength = Math.max(maxLength, visited.size());
} else {
while(s.charAt(aPointer) != s.charAt(bPointer)){
visited.remove(s.charAt(aPointer));
aPointer++;
}
visited.remove(s.charAt(aPointer));
aPointer++;
}
}
return maxLength;
}
}
@@ashokred it won't fail.
I searched for a logic almost half a day. You have helped to pick the logic to solve this problem. Thank you so much :))))
Awesome explanation man!! Just that you missed two test cases: if(s.isEmpty()){return 0;}
if(s.length()==1){return 1;}
He didn't miss those cases. His solution returns 0 for empty string and 1 when the string length is 1
Thanks! It's one of the simplest codes of this question I've seen so far.
I love you!!! I may not pass my interview but the knowledge you are here giving away for free is amazing!
Thanks. I love you too
Algorithm of the day. Awesome job buddy... Keep up the great work.
suppose string is "bacad", now when b pointer is at index 3 (when a comes 2nd time), this algorithm will remove b from the sliding window leaving string a ""aca" in it and still it has repeating character a.
Please correct me if I am wrong.
The remaining string will be "aca", that's right. Keep going through the while-loop though. On the next iteration of the while loop, b_pointer will still be at the second "a". Since "a" is still in the hash_set, the code will go to the else block, remove "a" from the hash_set, and increment a_pointer.
Then, you're left with "ca". Notice that b_pointer is still at "a". So in the next iteration, it will add "a" to the hash_set again since we're still at that char and we've just removed the other "a".
Thanks for the explanation, this problem took me a while to understand lol.
While trying the solution on my own, I stumbled across how to eliminate duplicate characters from a string. So, now, thanks to your video I can do both. :)
Same. Nick is legit
Question, if a duplicate occurs is it always the character at a_pointer that can be duplicate.
Eg Say if I have "abcdb", my a_pointer is at 0 and b_pointer is checking window.
After 'd', it encounters 'b' however popping character at a_pointer(which is 'a') results 'bcdb' which still has duplicates..??
If duplicate occurs, is it always same character at a_pointer which can be duplicate..??
I see your point -- the fact is Nick didn't explain this part clear enough. Beware of the fact that b_pointer will not move unless the duplicate is cleared. So you can see it as a continuous loop until the duplicate at b_pointer is found and removed from the substring, then the b_pointer will go on incrementing. Otherwise, a_pointer is just going to continue moving right while b_pointer sits still, letting the substring shrink every iteration.
@@ianpan0102 Make sense . Thanks for explaining. Until whatever duplicate is removed only "else part" is executed shrinking the hash . Finally after duplicate is removed, b_pointer will progress again.
@@SK-lu7ci You're welcome
@@ianpan0102 thanks I had the same question after I went through the solution
He didn't explain but the code does remove until that duplicate is removed.
Probably the easiest explaination :) This really helped me understand the sliding window problems.
I'm watching your videos because i just graduated and I'm preparing for these tough ass interviews. Your videos are nice and helpful. I wish I could do these problems by myself lmfao. You got any tips on how to get better at ACTUALLY coding these problems? I feel like I try and I don't get it and I tend to get frustrated and give up haha
Abdul Ahmed number 1 tip - don’t sit there and try and solve it. Just look at the solutions and learn
@@NickWhite I'll try that out thanks for the reply
...also after you've completed a few, you'll have a basic understanding that most of the questions following the same principles which allow you to solve similar questions with the same or slightly different solutions.
@@NickWhite what if I keep looking at solutions then? I sometimes feel that if I have to lookup solution, it is kinda cheating and not the natural process of learning.
@@fake_tourist think of it like cheating but to alter the natural process of learning in a positive direction.
You are awesome, I trying to understand this for hours, and you just make it easy in 8 minutes. Thank you.
Thanks man!
I tired to solve this problem over 1 hour... I thought I made a right solution and submitted ,
Time Limit Exceeded baaaam!!!!!!!!
Hey thanks for the explanation. Could you tell me how does it work for this test case: "pbbbyylmkbn"
I have the same question. Basically, if the repeating character is not the first element in the subset. I think the algorithm cannot handle.
Take "pww" for example. If the b_pointer encounters w, at index 2, we will remove "p" from the set. At this time, the set is [w], and b_pointer still points to the "w" at index 2. After removing "p", since the set still contains the value of b_pointer, we will again removing "w" from the set. Now the set becomes []. The two pointers both point to the index of 2, and we add the w at index 2 to the set.
@@tddod5060 Spot on. It's a wrong algo. I'm wondering how it worked at his end?
Me wondering too
I think this can be fixed by using an array instead of a hashmap. The big problem is the complexity would go up big time
I might be missing something but suppose you had something like : "abbcd" how would this system detect that there is a repeat. Because it would just see that there is no a repeat and it would just go through?
Would you say time complexity is O(n) and space complexity is O(1) constant space, because no matter how long the input string can be, at any given time the worst case extra space we're dealing with in the hashset is 26 characters?
Right
W8, but there are “while” loop and inside “contains” method that has O(n) complexity. So, at the end we solution with O(n^2) time completely
@@niiazemiluulu9987 Hashset contains method has time complexity O(1). so time complexity will be O(n)*O(1)=O(n).
I watched few videos for this question. this solution is so genius!!! Thank you for your video!
u keep sating it is easy but it wasnt easy until you showed me.
XDDD
One improvement I would suggest, in the else-clause when the character is found in the set, instead of removing it simply increment both a_pointer and b_pointer. You're going to end up writing the value back in the set next loop iteration anyways, so you can save yourself a cycle.
It will fail, if we have input like abcabcdbbef. It you won't remove char, then output will be 6.
bug : try this input " abcabkabc"
when b_pointer at 7 , it will remove a_pointer at 3 . the set will have "abka"
It works - b_pointer doesn't increment. Try to step through in a debugger.
What if there is an empty strings is present in s variables will the code executes???
When we get to a character that is already in the set, how do we know that the last time we seen that character it was at the index of a_pointer? I am a bit confused as to how we know that always removing the character at a_pointer from the set will always be the duplicate character? Like how do we know the duplicate character is not any other character between a_pointer and b_pointer?
very clear and concise! thank you!! it was super helpful : )
Much easier to understand than the explanation in Grokking the Coding Interview.
Nice. Thank you. You can also add a while loop on your else statement to make it a little faster.
while (hash_set.contains(s.charAt(b_pointer))) {
hash_set.remove(s.charAt(a_pointer));
a_pointer++;
}
Real curious.
Why adding a while loop making it faster? Does it add more complexity to the code?
Just curious, why didn't you try to improve your runtime on this one?
Thank you for the video,
I wish that you ran the code to give it a test and also see that there a miniscule typo in it.
But, that does not change the fact that the solution is straightforward.
Everytime I start practising for interviews I get stuck on this question but Nick White always helps
Yes! Great video. I shall continue on my journey - no nervous breakdown tonight. lol. Thanks man :)
Useful for explaining the "sliding window" solution, ty!
how about "abbcc" since you a_pointer index is zero and the duplicate character is in index 1 ?
This is a very straightfoward solution and approach to the problems. Could anyone verify with me the time complexity is O(N) and space complexity is O(N) because of the size of HashSet?
Excellent explanation.. Liked it. You don't have to worry about the errors, it happens with everyone. You are making us understand and explaining the alogorithm so well - that's the most considerable and fabulous thing.
The easiest explanation out there. Thank you very much.
Guys, I understand why we remove character in else clause but why we remove character in a_pointer. I was expecting to remove b_pointer since we check if character in b_position is present in Hashset? What if string is dbcabcbb? when you found b is already in Hashset you'll have to remove d at the beginning. We should've remove b, right?
Thanks Nick! You made problem so easily explained !!You are genius Man.
Thank u. Spend the hole day trying to understand it.
Say the given string is "abbb"
According to the code in the video - a_pointer and b_pointer = 0;
first - 'a' gets into the hashset, next - 'b' gets in. So far OK. (a_pointer is still 0 and b_pointer goes to 2)
Then, the second 'b' arrives - now 'b' already exists in the set, so it goes to the else part and removes s.chartAt(a_pointer) which is 'a'????
It should be removing 'b'!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! Though the max variable helps get the answer, is the procedure right?
Why can't we solve it with only one pointer and a set? One pointer iterates through the array meanwhile adds the chars into a unique set. Then whenever we see the same char (if it can not be added into unique set) we get the max length and clean the set. Then continue until the end of the array.
Why remove @a_pointer? Is it because we have to find the last occurence of current char in hash to deduce length? Also we can do this max = ((b_pointer- a_pointer)>max)? (b_pointer - a_pointer):max; for max isn't it?
Does this work for the input string as "dvdf". leet output return is 3.
I enjoyed this explanation. Thanks so much!
Hey Nick kudos to you great work ! i would appreciate if in evry video you can also explain time and space complexity of the sol
why do we use the hashset.remove function in else part
Solution is good but what if we replace string S="abcabcbb" to S = "abcbacbb"
then the above solution will remove 'a' instead of 'b' because of a_pointer.
string s = "abcbacbb";
if (s.Length == 0) return;
int result = 0;
int[] cache = new int[256];
for (int i = 0, j = 0; i < s.Length; i++)
{
j = (cache[s[i]] > 0) ? Math.Max(j, cache[s[i]]) : j;
cache[s[i]] = i + 1;
result = Math.Max(result, i - j + 1);
}
Exactly !!! Thats what i was thinking
I was thinking the same but then I saw "b_pointer is only increased while adding to hash set" otherwise "it will keep going to else statement and carry on deleting and increasing a_pointer". Also to maintain insertion order LinkedHashSet is used which is missing.🙂
thanks for explanation, was stuck at this problem for a long time
thanks nick this explanation is great
mylogic and this logic 100'% sync
i regret why I didn't come on this video at first place
else block needed more explanation though dry run gives the logic
Incredibly nice explanation! Hats off to you!
I think there is something wrong with your solution. If there is a string "pwwkew", when your left pointer points to the "p" and the right pointer point to the second w, the HashSet will remove "w". However, at this time, your left pointer is pointing the first " w " and the right pointer is pointing the second" w ", and the letter "w" is not in the HashSet.
Hey man you should be popular. Your explanation is much better than others. Your channel should hit 1 million
This is Gold! Thanks! So clear! Thanks Nick!
Great job, Nick. It's well explained.
So why are you removing "a" pointer when hashset contains element pointed by "b" pointer?
Meaning, if i deal with "abcbc"
when the end is at second"b" your algorithm removes a
just wanted to understand why
What I think happens, in the case of "abcbc" where the duplicate character is not the first character, each loop, an element will be removed until the duplicate character is removed. So yes the "a" will be removed when we have the second "b" but then on the next loop, the first "b" will be removed as well so then our hash set will just be "c" at which point it will try to add the second "b" again and will be successful since the first "b" was removed.
to decrease the size of set
I naturally gravitated towards the same solution, but I think left pointer and right pointer runs over the same element twice which makes this solution not the most optimized one. It is still an O(2n) solution which is not bad but it could be better.
when you delete the key in the hashset -- aren't you supposed to add it back for the same char but at a newer index?
sorry never mind... I didn't realize we are not incrementing the end in the else part
Thanks man for this straightforward answer!
Very nicely done.
But I think there is one issue with the substring content.
After finding a repeated char, shouldn't a_pointer be set to the next index after the first index of the repeated char?
Since we are not incrementing b_pointer in case of a repeated char, the next couple of iterations will use the same repeated char and move the a_pointer to the next index after the first index of the repeated char.
@@iUwej-y8d thanks!
Thanks man. This solution is way cleaner
Can you implement in cpp?
Thank you , you are doing great man .. this videos are very helpful ..!
Beautiful explanation man!
This is completely wrong. Advances the left index by 1, assuming that the repeated character is always there, but it might be anywhere in the substring.
I'm thinking the same thing
It isn't explained, but since the right index isn't incremented the loop checks the set again for the duplicate. The idea is that it shrinks the window from the left until the duplicate is removed and the current letter that triggered the duplicate found condition can be inserted into the set. This gives it a similar operation to using a map to index each letter and then shrink the window to the index following a duplicates last seen index. The difference being with a map you can immediately shrink the window to the new size rather than decrement the window until you find the new size.
Explained well. But the string we are getting at the end in hashset is not the expected string always. As we are returning the max size of the substring which is still intact because of the the Math() (max) operation.
could you draw the solution for better visualization? like where the pointers are currently at now etc. ?
Yea. it will be helpful if we can draw and explain
How to write that Java code in Python? I have searched many webs but have found no concise Python Solution. Thanks very much in advance.
There are different tricks in Python that aren’t exactly similar to Java code, what you can do is look at this exact question on leetcode then look in the discussion comments and look at the python solutions people have come up with. That should help
Eh, Idk, maybe just write it in python following the same logic line by line?
Following works, everybody.
def lengthOfLongestSubstring(self, s: str) -> int:
if (len(s) == 0):
return 0
left = 0
right = 0
ls = list(s)
longest_set = set()
longest = 0
while right < len(ls):
if ls[right] in longest_set: # If duplicate seen, two type of "duplicate seen"
longest_set.remove(ls[left]) # very important, remove the left pointer element
left += 1
else: # ls[i] not in longest_map, aka see a new character non-duplicate
longest_set.add(ls[right])
longest = max(longest, len(longest_set))
right += 1
return longest
Is this finding the sub-string or the sub-sequence, I think the solution above fails for few cases. Has anybody noticed ?
Can some one explain the me reasoning behind removing the header of the set when we encounter a existing character .
It also confuse me, I think remove the head is wrong.
I don't get it either bro, rip
Thanks a lot Nick. This is really nice and concise... O(n) time and won't take too much space...
public static int lengthOfSubString(String input){
List subString = new ArrayList();
Arrays.asList(input.split("")).forEach(val -> {
if (!subString.contains(val)) subString.add(val);
});
return subString.size();
}
Man that's a sweet solution to the problem
This was excellent! Just one question, wouldn't you want to remove the charAt(b_pointer) from the HashSet instead of a_pointer? For instance, for a string abcc, when you see the second 'c', you'd actually be removing 'a', correct?
He doesn't explain it, and there are other videos that do, but since it removes a and doesn't increment the b pointer it would check again and then remove b, and then c until only that 2nd c remains and the substring checks continue. The idea is that the window grows to the right (bpointer) as long as characters are unseen and shrinks from the left (apointer) until the duplicate that triggered the shrink gets removed. Leaving you to find the longest substring based on the size of the window.
in the example of pwwkew first iteration will be : storing p and then storing w and then removing w so I increment , so now j will be indexed to W it will add it to the set , now we have w k e but then we have w so we gonna remove it from the set , finally we gonna get only ke which is not correct
You could move the a_pointer to the index after the first repeating character, instead of traversing the sequence, that would skip a lot of iterations!
What if the input was "abcade"?
FrZn it would still find “bcade” :)
FrZn the a_pointer would move from a to b
FrZn here is a better input to illustrate that: abcDefgDhijklmnop
FrZn first iteration would start in a, second in e, skipping 3 iterations
How it works for pwwkew??
First we have "pw" in the Set and max is 2 at this point,
then we see another "w", we remove p and increment a pointer, set contains only w
we add k, set is "wk"
we add e, set is "wke" and max will become 3
we see "w", remove the "w" and max is still 3
This got me stuck too. He didn't explain the "pwwkew" part. You need to run debugger (or by hand) to walk it through to kinda grasp it. Apparently the same logic works for pwwkew too.
Simplest way.. Very clear thanks
you are the best Nick :) Thank you!
This does not work for string "Clementisacap ", mentisac answer should be 8 , i get 10 as max
I have a question about LeetCode in general... Are people expected to derive these out by themselves, coming up with the sliding door idea from nothing, or do most people learn how to implement it through a video like this?
people know from doing them
@@NickWhite HashSet contains unique values then what's the need to remove characters from it?
@@NickWhite also what's the need for max hashset size will return the same value?
well explained thank you so much Nick
this solution applies sliding window strategy. It can be solved recursive, so memoization too.
Doesn't work for "pwwkew", solution doesn't ensure that the hash set contains a substring. It will keep 'p' in the hashset unti the next p, but if there isn't one, your final max will be 4 as you can have a hashset p,w,k,e when it should hbe w,k,e (or k,e,w). Since youtube deleted the dislike count, now a ton of newbies will think this is the correct solution and fail their interviews.
I just ran it with this example and it absolutely does work.
@@diamondlee478 strange , look at comments . Other people have the same issue but also just look as the logic I wrote, does it not make sense?
Bro , solution is correct.when 'p' comes it adds it in set incrementing "b"(b at 1),when next character 'w' comes it also added in set ,incrementing the "b"(b at 2) ,max value =2,now when the second 'w' comes it removes the character at "a"(0) position which is 'p' incrementing "a"(a at 1) and set size is now=1 and when we iterate again at b index it is still 'w' so remove 'w' from set now the set size is zero,when we iterate again as 'w' is not in set it added in set incrementing b.
likewise the code runs.
@@hey-cg3fv look all I know is I run this on leetcode and that’s the input that failed, try it yourself
@@saipeor I run this code yesterday it executes perfectly
Wrong Answer:
Input:
"pwwkew"
Output:
4
Expected:
3
Yes there are more things to do in else block for it it work. I was doing it in PHP so slightly different but in the else block I had to cut out the string from the found letter until the end plus add the found letter to the end of the string and then it worked. The basics of the examples and the way of thinking are good though in the video.
your solution not working for "abcabcbb" can you please correct me
This solution does not work with PWWKEW
qrsvbspk
Can you explain for this input please ?
what is the output and how?
It's 5: "qrsvb" is the longest substring. If you add the 's' after 'b', you get a repeating character. All other substrings without repeating chars are shorter than this one.
@@MoaazAhmad vbspk also mate ✌️
Nice video! Thanks Nick!
Nice piece of code dude
thanks.....this helped me a lot😁😁
instead of contains method, if we use directly add , then we can reduce one line
if(set.add(s.charAt(rightPointer))){