LeetCode Longest Substring Without Repeating Characters Solution Explained

No video

LeetCode Longest Substring Without Repeating Characters Solution Explained - Java

Рет қаралды 200,643

Күн бұрын

The Best Place To Learn Anything Coding Related - bit.ly/3MFZLIZ
Join my free exclusive community built to empower programmers! - www.skool.com/software-develo...
Preparing For Your Coding Interviews? Use These Resources
--------------------
(My Course) Data Structures & Algorithms for Coding Interviews - thedailybyte.dev/courses/nick
AlgoCademy - algocademy.com/?referral=nick...
Daily Coding Interview Questions - bit.ly/3xw1Sqz
10% Off Of The Best Web Hosting! - hostinger.com/nickwhite
Follow Me on X/Twitter - x.com/nickwhitereal
Follow My Instagram - / nickwwhite
Other Social Media
----------------------------------------------
Discord - / discord
Twitch - / nickwhitettv
TikTok - / nickwhitetiktok
LinkedIn - / nicholas-w-white
Show Support
------------------------------------------------------------------------------
Patreon - / nick_white
PayPal - paypal.me/nickwwhite?locale.x...
Become A Member - / @nickwhite
#coding #programming #softwareengineering

Пікірлер: 260

@arunsp767 2 жыл бұрын

A very important correction. Not in the code, but in the explanation: We use Set NOT because it stores unique characters, but because (in HashSet) the operation 'contains()' runs in O(1). We really don't need a data structure that maintains unique elements because we are doing that part explicitly using the 'contains()' operation. So the code would run fine even with a regular List. But 'contains()' in List is typically O(n). Hence the choice of (Hash)Set

@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 11 ай бұрын

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

@MrMakemusicmike 3 жыл бұрын

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.

@utkarshpant5297 4 жыл бұрын

Thank you man... I was smashing my head over this problem for more than 3 hours

@ryzurrin 2 жыл бұрын

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!

@btsforever7815 2 жыл бұрын

you are single-handedly carrying my leetcode journey, thank you so much!

@mikasaackerman2694 4 жыл бұрын

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

@albertgao7256 3 жыл бұрын

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

@Blure 4 жыл бұрын

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

@jibinkjose1073 3 жыл бұрын

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 2 жыл бұрын

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

@dimka781 11 ай бұрын

@@ashokred it won't fail.

@sanjayizardar2263 4 жыл бұрын

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

@misokwon4713 4 жыл бұрын

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

@rushm6684 2 жыл бұрын

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.

@chathrapathis1110 Жыл бұрын

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

@ranaalameedee9762 2 жыл бұрын

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

@steeck1 3 жыл бұрын

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

@user-gi2sb8xr8f 4 жыл бұрын

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

@Minte123 3 жыл бұрын

XDDD

@jpenber5418 3 жыл бұрын

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

@rishabhsahu5257 3 жыл бұрын

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

@sajalsingh7768 3 жыл бұрын

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

@TheSmashten 2 жыл бұрын

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 2 жыл бұрын

the max stores the maximum of hashset size and current max..also note we have to check each and every substring.

@yvoonetao4288 2 жыл бұрын

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

@adrijaroy4499 2 жыл бұрын

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

@yeojinha930 3 жыл бұрын

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

@pealhasan 7 ай бұрын

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

@M240Waheed 4 жыл бұрын

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 4 жыл бұрын

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

@user-kd1du1yp4g 3 жыл бұрын

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

@abdullahbabor4876 3 жыл бұрын

Incredibly nice explanation! Hats off to you!

@sarahy5991 2 жыл бұрын

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

@Kidkromechan Жыл бұрын

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?

@narasimhakamath3808 2 жыл бұрын

The easiest explanation out there. Thank you very much.

@raxit2684 3 жыл бұрын

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

@julietgeorge4858 4 жыл бұрын

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

@bossman4112 3 жыл бұрын

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?

@cryptojeff3993 2 жыл бұрын

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

@imykeX 3 жыл бұрын

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

@nikhil-saxena 4 жыл бұрын

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

@SK-yb7bx 2 жыл бұрын

Great job, Nick. It's well explained.

@eshagupta9407 4 жыл бұрын

Beautiful explanation man!

@uk1523 4 жыл бұрын

Can you implement in cpp?

@dalbirsinghdhillon1429 3 жыл бұрын

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

@Ben-pb7ct 3 жыл бұрын

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?

@saderied8719 8 ай бұрын

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?

@moonmaster36 2 жыл бұрын

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

@eugenek951 Жыл бұрын

I enjoyed this explanation. Thanks so much!

@TheKillermob13 3 жыл бұрын

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.

@aartikelkar397 4 жыл бұрын

Simplest way.. Very clear thanks

@fatimaibrahim-biangoro9607 4 жыл бұрын

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

@williengangamacharia2761 2 жыл бұрын

Thanks man for this straightforward answer!

@prachisharma7500 Жыл бұрын

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

@nguyentuan1990 2 жыл бұрын

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

@vipulkrishna19 4 жыл бұрын

Best explanation

@mattgervasio3798 4 жыл бұрын

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 4 жыл бұрын

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

@dineshmaddisetty2545 2 жыл бұрын

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

@sidikridwan Жыл бұрын

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

@kuttikrishnankodoth1463 2 жыл бұрын

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

@henryborska9098 3 жыл бұрын

Thanks man. This solution is way cleaner

@blancosj 4 жыл бұрын

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

@RA-nt1hj 3 жыл бұрын

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

@Moosorkh 2 жыл бұрын

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.

@amansingh.h716 3 жыл бұрын

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

@angelbythewings 3 жыл бұрын

Man that's a sweet solution to the problem

@Prince-fv8mb 6 ай бұрын

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

@iubob98 4 жыл бұрын

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

@damodharreddypannala3604 2 жыл бұрын

well explained thank you so much Nick

@codingpros4391 4 жыл бұрын

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

@janmichaelaustria620 4 жыл бұрын

Nice video! Thanks Nick!

@madanmohanpachouly6135 2 жыл бұрын

Nice explanation, Thanks.

@angkits9709 4 жыл бұрын

How can we calculate the time complexity of the code ?

@nishantingle1438 2 жыл бұрын

else block needed more explanation though dry run gives the logic

@shanthureddy4234 2 жыл бұрын

Thank you for the explanation ...

@senaokumus9548 Жыл бұрын

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?

@johnangelo2000 2 жыл бұрын

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?

@allthingsuseless4707 2 жыл бұрын

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.

@lokeshguru413 3 жыл бұрын

Good explanation. Thanks

@ArifRahman-nb3ff 2 жыл бұрын

you are the best Nick :) Thank you!

@bspuneeth9523 3 жыл бұрын

Nice piece of code dude

@jeezradz 4 жыл бұрын

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

@90krishika 4 жыл бұрын

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.

@vagabond_in_a_box852 3 жыл бұрын

what a fine explanation!

@raam2508 3 жыл бұрын

best explanation !! cheers :)

@deepakkumar-zk3hb 4 жыл бұрын

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

@samyboy981 3 жыл бұрын

Great Solution!

@shaileshhegde9205 4 жыл бұрын

Well explained!

@deekshaagrawal1111 Жыл бұрын

thanks Nick!!

@kevinrodriguez7403 3 жыл бұрын

ok this was a great explanation.

@MAGAVISHNUT 4 ай бұрын

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

@kks2105 2 ай бұрын

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

@raghulkrishnanb8919 3 жыл бұрын

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?

@abishaisingh5561 3 жыл бұрын

can you do that in c++ ?

@meriyemelhajoui4083 9 ай бұрын

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

@myjava2844 2 жыл бұрын

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

@SK-lu7ci 4 жыл бұрын

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.

@qingyachen3990 2 жыл бұрын

very clear and fast!!!

@darwinanirudh1793 4 жыл бұрын

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

@sowmyasg8127 4 жыл бұрын

please do videos on hackerrank graphs topic in interview kit

@mathssr Жыл бұрын

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.

@rushabhjaiswal1442 4 жыл бұрын

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