@@pandu7820 class Solution: def lengthOfLongestSubstring(self, s: str): if len(s) == 0 or s == None: return 0 i = 0 j = 0 max_value = 0 set1 = set() set1 = set() while i < len(s): char = s[i] while char in set1: set1.remove(s[j]) j = j + 1 set1.add(char) max_value = max(max_value, i - j + 1) i = i + 1 return max_value p = Solution() s = "pwwkew" result = p.lengthOfLongestSubstring(s) print(result)
Wow! This explanation really resonated with me. Not to sound overly dramatic, but for me, this was a great programming performance. Excellent "whiteboard" explanation, along with the followup explanation while coding to reinforce what was discussed on the whiteboard. All accomplished in about 10 minutes.
Thank you very much! I'm glad you got some use out of it, since most of us (including myself) are visual learners, it makes the most sense to have full animated examples.
the double while loop increase the time complexity to O(N2), the concept behind the sliding window approach is to slow down the finding of substring. If you have a string of 1000 charcater it increase its time complexity to 1000 * 1000 = 1000000
function findLongestSubstring(str) { let longest = 0; let seen = {}; let start = 0;
for (let i = 0; i < str.length; i++) { let char = str[i]; if (seen[char]) { start = Math.max(start, seen[char]); } longest = Math.max(longest, i - start + 1); seen[char] = i + 1; } return longest; } this is write in javascript and have time complexity of O(N) which means that the time complexity of the algorithm is linear (with the number of char in the string)
Thanks! It is important to understand that when a repeating char is found (e.g. i = 2, ch = second 'W'), all chars in the current SW that appear before this repeating char also have to be removed (and then we remove the repeating char). However, the whole SW is not erased -- the chars after the repeating char (that was removed) still remain in SW. e.g. if there was a 'A' between the two W's, then the SW will change from "PWA" to "AW".
Got this question on an interview. I knew sliding window was the approach, but I couldn't get it in time. I never thought to implement it with two pointers as you did here. Thankfully I've moved onto the next stage of the hiring process, but if I ever see this problem again, now I'll know an easy solution! Thanks.
I know im asking randomly but does any of you know of a tool to log back into an Instagram account?? I somehow forgot the password. I would appreciate any tricks you can give me
I don't see how it is linear. When we have a conflict - found a repeated character - we need to trim the prefix of the string from our set until the conflict goes away. That takes n1*O(1), where n1 < N is the length of the prefix being removed. (Ignoring for now the fact that worst case for removal from set if log(size)) And we need to do it as many times as there are conflicts. Which is n2 < N. Which in total still gives us O(N**2).
I was wrong. At max, we only add s.size() = N characters to the set, and we can only remove at most N. So as long as set removal is assumed to be O(1), total complexity is O(N).
Superb breakdown. I was able to follow everything up til the time & space complexity part. Could someone please explain why it's not O(n^2). I know he explained it, but it's just not clicking for me. He described it well, but I can be kinda slow at times.
Nice explanation . very useful . Thank you . Please explain , how can a while loop inside a while loop did not cause O(n^2) time complexity . really confused at that part . Jason Jason 3 months ago The inner while loop will only iterate once through the every char of the string. It does not keep looping for every iteration of the outer loop. Hence it is O(2N). Hope it helps! TJ Tolton TJ Tolton 1 month ago a critical clue about the time complexity here: when j advances forward, i does NOT go back to j and start iterating from there. it stays where it is -- otherwise it would be O(n^2) from older comments :)
Finally understood this algorithm after one full day . Great explanation:)
The same bro, spent almost a day to understand. )))
Fantastic animation. It makes the explanation clearer and better.
literally THE BEST explanation on RUclips for this LC question. Thank you, Michael
Was confused a lot with this problem.. You made it very simple. Thank you so much! Keep up the good work.
Clean and concise explanation, very helpful. Thank you :) Never understood the concept of the sliding window better! Kudos! (y)
Awesome, im so glad the video helped you!
@@AlgosWithMichael can you code this in python
@@pandu7820 class Solution:
def lengthOfLongestSubstring(self, s: str):
if len(s) == 0 or s == None:
return 0
i = 0
j = 0
max_value = 0
set1 = set()
set1 = set()
while i < len(s):
char = s[i]
while char in set1:
set1.remove(s[j])
j = j + 1
set1.add(char)
max_value = max(max_value, i - j + 1)
i = i + 1
return max_value
p = Solution()
s = "pwwkew"
result = p.lengthOfLongestSubstring(s)
print(result)
Thanku so much bro! I watched multiple videos to try and understand the algorithm of this problem and gotta say your video was the most helpful atm
ruclips.net/user/maksrane100 check this too
Wow! This explanation really resonated with me. Not to sound overly dramatic, but for me, this was a great programming performance.
Excellent "whiteboard" explanation, along with the followup explanation while coding to reinforce what was discussed on the whiteboard.
All accomplished in about 10 minutes.
Thank you very much! I'm glad you got some use out of it, since most of us (including myself) are visual learners, it makes the most sense to have full animated examples.
the double while loop increase the time complexity to O(N2), the concept behind the sliding window approach is to slow down the finding of substring. If you have a string of 1000 charcater it increase its time complexity to 1000 * 1000 = 1000000
function findLongestSubstring(str) {
let longest = 0;
let seen = {};
let start = 0;
for (let i = 0; i < str.length; i++) {
let char = str[i];
if (seen[char]) {
start = Math.max(start, seen[char]);
}
longest = Math.max(longest, i - start + 1);
seen[char] = i + 1;
}
return longest;
}
this is write in javascript and have time complexity of O(N) which means that the time complexity of the algorithm is linear (with the number of char in the string)
The video editing made this extremely enjoyable and easy to follow. Thumbs up from me
Much appreciated!
Thank you so much. I have seen almost 10 videos on understanding this question but this was the best explanation for this question.
That's the best explanation which I found on youtube
Wow, thanks!
Thanks! It is important to understand that when a repeating char is found (e.g. i = 2, ch = second 'W'), all chars in the current SW that appear before this repeating char also have to be removed (and then we remove the repeating char).
However, the whole SW is not erased -- the chars after the repeating char (that was removed) still remain in SW.
e.g. if there was a 'A' between the two W's, then the SW will change from "PWA" to "AW".
Exactly, nice explanation.
How's that implemented?
Top notch algorithm solution explanation! Could not have asked for any better. Be blessed!
the new video style with animation makes the problem be easier to understand. Thank you
Awesome glad it is helpful!
Your videos are very intuitive and easy to understand. I really appreciate your work dude.
I appreciate that!
First time I ever heard about sliding windows. I was completely clueless. This content is subscription worthy, thanks!
Best sliding window explanation in the internet, please make more algorithm explanation videos.
Got this question on an interview. I knew sliding window was the approach, but I couldn't get it in time. I never thought to implement it with two pointers as you did here. Thankfully I've moved onto the next stage of the hiring process, but if I ever see this problem again, now I'll know an easy solution! Thanks.
By using diagrams is very simple to understand...many thanks!
Highly appreciate the way you made this algorithm so easy. Commendable job. Thanks !
Thank you so much, I was waiting for this technique for so long.
You're very welcome!
The most underrated technical channel, you are doing a awesome awesome awesome job men...
Thank you so much!
The explanation with the animation was incredibly well. Keep it up bro 👍.
you're saving lives out here man. keep up the good work!!
Finally, I understood the concept.
Your video on this topic helps a lot with my understanding. Thank you!
I'm so glad!
The clearest explanation I have come across so far. Thanks!
Wow..What an Explanation ! Became Fan of you!
Great explanation. We could also just use set.size() to update max rather than i - j + 1. The set will always contain unique elements.
Yep good point
Your videos are like super. And after watching your video the fear of coding likes gone...
That is amazing! I'm glad it helped you
This is the best video of sliding window algorithm in youtube.Thanks alot.
Glad it was helpful!
Thankyou ! you got a new subscriber,
I was just exploring the explanation from last 6 hours
and finally, your video helped me a lot...
tysm !!!!
Thank you for watching and subscribing!
Great solution. Logic was super easy to follow and understand where you were going.
the explanation is just brilliant, thank you!!!
ruclips.net/user/maksrane100 check this too
Absolutely brilliant Michael!
Thanks for giving a clean solution!!
Best explanation about sliding window,,, thanks man 😎
thank you for explaining it was very helpful please make more such videos. thanks again.
Great stuff, thanks. The animation makes it so much easier to grasp.
Awesome!
bruh.. make more videos like this and i'll like and comment on every single one! Thank you!
Haha most definitely
so much better than the other videos for this problem
I appreciate that
dude you are awesome! you always have the best explanation for any problem as compared to other youtube videos.
Thank you very much!
clean, smooth and easy explanation.
Loving your content. Thank you for making these videos!
My pleasure!
I know im asking randomly but does any of you know of a tool to log back into an Instagram account??
I somehow forgot the password. I would appreciate any tricks you can give me
Super clear with your animated explanation.
Glad to hear that!
Incredibly helpful and easy to understand. THANK YOU!
Of course!
You're awesome man. clearest explanations I've seen
I appreciate that!
Once again, great explanation and the demo before really helps a lot!
Glad to hear it!
Best Explanation !
You are just Amazing. You made it so simple for every one to understand. You deserve more subscribers :-)
Thank you so much 😀
This was really good, well done dude!
Glad you enjoyed it!
Thanks! I like this explanation a lot more than the one in Grokking the Coding Interview and it was illustrated quite nicely. Gave a like.
Thanks!
Amazing explanation. Best video about sliding window.
Thank you, I appreciate that!
Thank you Micheal
Great explanation. Thanks
Great explanation. You make difficult things look easy
Thank you so much!
Awesomely simple approach.. I love your explanations.... liked --subscribed and looking forward for more like this..
More videos to come, thanks for subscribing!
Nice explanation and thanks for describing time and space complexity.
Of course, it is very important to know!
Best explanation seen so far, thanks for video :)
Glad you enjoyed it!
I don't see how it is linear. When we have a conflict - found a repeated character - we need to trim the prefix of the string from our set until the conflict goes away. That takes n1*O(1), where n1 < N is the length of the prefix being removed. (Ignoring for now the fact that worst case for removal from set if log(size))
And we need to do it as many times as there are conflicts. Which is n2 < N. Which in total still gives us O(N**2).
I was wrong. At max, we only add s.size() = N characters to the set, and we can only remove at most N. So as long as set removal is assumed to be O(1), total complexity is O(N).
nice one bro, subscribed
this was exactly what i needed thank you! immediately subscribed :)
Thanks for subbing!
This is the best explanation I have seen, Thank you very much!! I'm Subscribing
Anytime man!
Very useful video. Thank you bro
I really like your explanations and that you code in Java.
awesome video. Thanks for the great explanation
My pleasure!
Nice explanation.. Thanks!!!
Great explanation, really easy to follow, thanks for your content and help :)
Glad it helped!
awesome video man! explained it so well thank you!
Accurate explanation...Thanks a lot
Thank you :)
It was very good one and easy to understand the problem . It helped a lot.
Nice, I'm glad!
Amazing explanation. Thanks
Super clear explanation! Thanks
Glad it was helpful!
@@AlgosWithMichael I watched this yesterday and was asked about the sliding window algorithm in today's interview.. ?!
thank you. Great explanation
You are welcome!
visualization helps. thanks !
Superb breakdown. I was able to follow everything up til the time & space complexity part. Could someone please explain why it's not O(n^2). I know he explained it, but it's just not clicking for me. He described it well, but I can be kinda slow at times.
Nice explanation . very useful . Thank you . Please explain , how can a while loop inside a while loop did not cause O(n^2) time complexity . really confused at that part .
Jason
Jason
3 months ago
The inner while loop will only iterate once through the every char of the string. It does not keep looping for every iteration of the outer loop. Hence it is O(2N). Hope it helps!
TJ Tolton
TJ Tolton
1 month ago
a critical clue about the time complexity here: when j advances forward, i does NOT go back to j and start iterating from there. it stays where it is -- otherwise it would be O(n^2)
from older comments :)
@@Akel4611 Okay, I get it now. Thanks for showing me these comments.
love your solution, easy to understand!
Glad it helped!
great content keep it up, buddy!
excellent animation easy understanding very welll....
Thanks for making videos with nice explanations.
Of course, thanks for watching
Thanks Man!!
Awesome explanation bro
Thank you 🙂
Awesome explanation. Thank you
Glad it was helpful!
thank you, i wrote the code for it b4 but it took n^2 time
HashMap map = new HashMap();
int top = 0, x = 0;
for(int i=0; i
This was a great explanation! Thank you!
Glad you enjoyed it!
ruclips.net/user/maksrane100 check this too
Subscribed!
Great video.
Thanks
cool explanation
Glad it was helpful!
Thank you.
Thanks!
Why can't we calculate max base on Math.max(max, set.length) instead of i-i+1?
You can do it that way as well, it is up to you!
Thank you this is so helpful!
Glad it was helpful!
best explanation ;)
Glad it helped!
Wish you could build 424. Longest Repeating Character Replacement problem with the same approach you described here.
Great explanation ! What software do you use to make these animation ? Thanks
u can use adobe premiere pro of filmora
@@زانغت_ساما thank you ❤️
amazing explanation . thankyou so much:)
Anytime!
great vid
Thanks!
Thank you for the video. I am simply curious about what is the underlying time complexity for function set.contains() and set.remove()
you are the best
Thank you!
Wonder why you need the inner while loop, I thought hashset wouldn't have a duplicate so no need to remove within a loop.