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

@tahaansari5621

2 жыл бұрын

I see u going on every video and commenting out the same thing. 😂 Anyway, really appreciate ur point.

@heathens2867

2 жыл бұрын

@@tahaansari5621 it's actually good because not everyone will watch his each and every video

@user-zw8uq1rj9m

2 жыл бұрын

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

@tomerharari633

Жыл бұрын

What's wrong with a hashmap though? because checking if hashmap contains a key is also O(1) isn't it?

@dimka781

10 ай бұрын

​@@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!

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!

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)

@ashokred

2 жыл бұрын

Ditto, this will fail for "aabaab!bb" unless this fix is applied :)

@kunalnarang1912

2 жыл бұрын

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.

@raghavendrayadalam7440

Жыл бұрын

I'm actually trying with map. can you please share code?

@punters4218

Жыл бұрын

@@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 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; } }

@dimka781

10 ай бұрын

@@ashokred it won't fail.

Thanks! It's one of the simplest codes of this question I've seen so far.

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

@manavmody4959

Жыл бұрын

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.

You are awesome, I trying to understand this for hours, and you just make it easy in 8 minutes. Thank you.

This code is obviously much readable than the official LeetCode solution, great job dude!

very clear and concise! thank you!! it was super helpful : )

Algorithm of the day. Awesome job buddy... Keep up the great work.

I searched for a logic almost half a day. You have helped to pick the logic to solve this problem. Thank you so much :))))

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. :)

@gradientO

Жыл бұрын

Same. Nick is legit

Thanks for the explanation, this problem took me a while to understand lol.

Useful for explaining the "sliding window" solution, ty!

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?

Everytime I start practising for interviews I get stuck on this question but Nick White always helps

I watched few videos for this question. this solution is so genius!!! Thank you for your video!

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?

Thanks Nick! You made problem so easily explained !!You are genius Man.

Does this work for the input string as "dvdf". leet output return is 3.

how about "abbcc" since you a_pointer index is zero and the duplicate character is in index 1 ?

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.

@TheDoubleMvp

3 жыл бұрын

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".

I love you!!! I may not pass my interview but the knowledge you are here giving away for free is amazing!

@mohdamirkhan6571

3 жыл бұрын

Thanks. I love you too

Thank u. Spend the hole day trying to understand it.

Incredibly nice explanation! Hats off to you!

Awesome explanation man!! Just that you missed two test cases: if(s.isEmpty()){return 0;} if(s.length()==1){return 1;}

@bethlehemyohannes200

Жыл бұрын

He didn't miss those cases. His solution returns 0 for empty string and 1 when the string length is 1

Hi! Can you please explain this same program by using the ascii code method?

This is Gold! Thanks! So clear! Thanks Nick!

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?

Just curious, why didn't you try to improve your runtime on this one?

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++; }

@giovankabisano2266

Жыл бұрын

Real curious. Why adding a while loop making it faster? Does it add more complexity to the code?

Can you implement in cpp?

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?

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?

@farhan787

4 жыл бұрын

Right

@niiazemiluulu9987

4 жыл бұрын

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

@rohitkasture0100

4 жыл бұрын

@@niiazemiluulu9987 Hashset contains method has time complexity O(1). so time complexity will be O(n)*O(1)=O(n).

why do we use the hashset.remove function in else part

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.

@amitverma0511

3 жыл бұрын

It will fail, if we have input like abcabcdbbef. It you won't remove char, then output will be 6.

Great job, Nick. It's well explained.

Thanks man for this straightforward answer!

Hey thanks for the explanation. Could you tell me how does it work for this test case: "pbbbyylmkbn"

@tddod5060

4 жыл бұрын

I have the same question. Basically, if the repeating character is not the first element in the subset. I think the algorithm cannot handle.

@albertli7044

4 жыл бұрын

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.

@mehulgala07

4 жыл бұрын

​@@tddod5060 Spot on. It's a wrong algo. I'm wondering how it worked at his end?

@andychang1179

4 жыл бұрын

Me wondering too

@faaith100

4 жыл бұрын

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

Probably the easiest explaination :) This really helped me understand the sliding window problems.

this solution applies sliding window strategy. It can be solved recursive, so memoization too.

u keep sating it is easy but it wasnt easy until you showed me.

@Minte123

3 жыл бұрын

XDDD

How can we calculate the time complexity of the code ?

Thanks a lot Nick. This is really nice and concise... O(n) time and won't take too much space...

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

@NickWhite

4 жыл бұрын

Abdul Ahmed number 1 tip - don’t sit there and try and solve it. Just look at the solutions and learn

@M240Waheed

4 жыл бұрын

@@NickWhite I'll try that out thanks for the reply

@justskillfull

3 жыл бұрын

...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.

@shikhindahikar8488

3 жыл бұрын

@@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.

@trailsnail

2 жыл бұрын

@@shikhindahikar8488 think of it like cheating but to alter the natural process of learning in a positive direction.

bug : try this input " abcabkabc" when b_pointer at 7 , it will remove a_pointer at 3 . the set will have "abka"

@ameynaik2743

3 жыл бұрын

It works - b_pointer doesn't increment. Try to step through in a debugger.

The easiest explanation out there. Thank you very much.

Simplest way.. Very clear thanks

Thanks man! I tired to solve this problem over 1 hour... I thought I made a right solution and submitted , Time Limit Exceeded baaaam!!!!!!!!

could you draw the solution for better visualization? like where the pointers are currently at now etc. ?

@Shiva-zy7jq

4 жыл бұрын

Yea. it will be helpful if we can draw and explain

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..??

@ianpan0102

4 жыл бұрын

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.

@SK-lu7ci

4 жыл бұрын

@@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.

@ianpan0102

4 жыл бұрын

@@SK-lu7ci You're welcome

@AtulDislay

4 жыл бұрын

@@ianpan0102 thanks I had the same question after I went through the solution

@jairambala4276

4 жыл бұрын

He didn't explain but the code does remove until that duplicate is removed.

Beautiful explanation man!

Yes! Great video. I shall continue on my journey - no nervous breakdown tonight. lol. Thanks man :)

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.

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?

@jeezradz

4 жыл бұрын

sorry never mind... I didn't realize we are not incrementing the end in the else part

Thanks man. This solution is way cleaner

What if there is an empty strings is present in s variables will the code executes???

Much easier to understand than the explanation in Grokking the Coding Interview.

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

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?

Thank you , you are doing great man .. this videos are very helpful ..!

I enjoyed this explanation. Thanks so much!

thanks for explanation, was stuck at this problem for a long time

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.

Very nicely done. But I think there is one issue with the substring content.

Nice video! Thanks Nick!

well explained thank you so much Nick

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

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.

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?

Man that's a sweet solution to the problem

Nice explanation, Thanks.

Can some one explain the me reasoning behind removing the header of the set when we encounter a existing character .

@zacharysong4863

3 жыл бұрын

It also confuse me, I think remove the head is wrong.

@IChowdhury01

3 жыл бұрын

I don't get it either bro, rip

you are the best Nick :) Thank you!

Best explanation

Thank you for the explanation ...

Good explanation. Thanks

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

@scotty8789

3 жыл бұрын

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.

@hey-cg3fv

2 жыл бұрын

to decrease the size of set

can you do that in c++ ?

best explanation !! cheers :)

After finding a repeated char, shouldn't a_pointer be set to the next index after the first index of the repeated char?

@MuneneJulius

3 жыл бұрын

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.

@lucasslf

3 жыл бұрын

@@MuneneJulius thanks!

thanks.....this helped me a lot😁😁

qrsvbspk Can you explain for this input please ? what is the output and how?

@MoaazAhmad

4 жыл бұрын

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.

@anuabraham2524

4 жыл бұрын

@@MoaazAhmad vbspk also mate ✌️

Is this finding the sub-string or the sub-sequence, I think the solution above fails for few cases. Has anybody noticed ?

Well explained!

what a fine explanation!

your solution not working for "abcabcbb" can you please correct me

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.

very clear and fast!!!

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?

@Chris-xr2bt

3 жыл бұрын

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.

Great Solution!

thanks Nick!!

Nice piece of code dude

else block needed more explanation though dry run gives the logic

please do videos on hackerrank graphs topic in interview kit

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.

@teshou4474

3 жыл бұрын

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

@Kai-iq2ps

3 жыл бұрын

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 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

Excellent video!