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)
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.
@@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)
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.
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".
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
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 :)
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).
Fantastic animation. It makes the explanation clearer and better.
Finally understood this algorithm after one full day . Great explanation:)
The same bro, spent almost a day to understand. )))
literally THE BEST explanation on TH-cam 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.
Thank you so much. I have seen almost 10 videos on understanding this question but this was the best explanation for this question.
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)
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
th-cam.com/users/maksrane100 check this too
Top notch algorithm solution explanation! Could not have asked for any better. Be blessed!
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.
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)
The video editing made this extremely enjoyable and easy to follow. Thumbs up from me
Much appreciated!
@@AlgosWithMichael Thank you for your hard work ! :)
Your videos are very intuitive and easy to understand. I really appreciate your work dude.
I appreciate that!
Best sliding window explanation in the internet, please make more algorithm explanation videos.
Absolutely brilliant Michael!
First time I ever heard about sliding windows. I was completely clueless. This content is subscription worthy, thanks!
the new video style with animation makes the problem be easier to understand. Thank you
Awesome glad it is helpful!
Highly appreciate the way you made this algorithm so easy. Commendable job. Thanks !
you're saving lives out here man. keep up the good work!!
Great solution. Logic was super easy to follow and understand where you were going.
The clearest explanation I have come across so far. Thanks!
The most underrated technical channel, you are doing a awesome awesome awesome job men...
Thank you so much!
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!
The explanation with the animation was incredibly well. Keep it up bro 👍.
Thank you so much, I was waiting for this technique for so long.
You're very welcome!
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.
That's the best explanation which I found on youtube
Wow, thanks!
the explanation is just brilliant, thank you!!!
th-cam.com/users/maksrane100 check this too
Your video on this topic helps a lot with my understanding. Thank you!
I'm so glad!
This is the best video of sliding window algorithm in youtube.Thanks alot.
Glad it was helpful!
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?
By using diagrams is very simple to understand...many thanks!
Great stuff, thanks. The animation makes it so much easier to grasp.
Awesome!
Wow..What an Explanation ! Became Fan of you!
Best explanation about sliding window,,, thanks man 😎
clean, smooth and easy explanation.
Thanks for giving a clean solution!!
so much better than the other videos for this problem
I appreciate that
thank you for explaining it was very helpful please make more such videos. thanks again.
Incredibly helpful and easy to understand. THANK YOU!
Of course!
dude you are awesome! you always have the best explanation for any problem as compared to other youtube videos.
Thank you very much!
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
You're awesome man. clearest explanations I've seen
I appreciate that!
Super clear with your animated explanation.
Glad to hear that!
Finally, I understood the concept.
You are just Amazing. You made it so simple for every one to understand. You deserve more subscribers :-)
Thank you so much 😀
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!
This was really good, well done dude!
Glad you enjoyed it!
Once again, great explanation and the demo before really helps a lot!
Glad to hear it!
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!
bruh.. make more videos like this and i'll like and comment on every single one! Thank you!
Haha most definitely
Best Explanation !
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.
this was exactly what i needed thank you! immediately subscribed :)
Thanks for subbing!
Thank you Micheal
awesome video man! explained it so well thank you!
Great explanation, really easy to follow, thanks for your content and help :)
Glad it helped!
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.. ?!
Nice explanation.. Thanks!!!
Great explanation. You make difficult things look easy
Thank you so much!
Very useful video. Thank you bro
love your solution, easy to understand!
Glad it helped!
awesome video. Thanks for the great explanation
My pleasure!
Best explanation seen so far, thanks for video :)
Glad you enjoyed it!
nice one bro, subscribed
This is the best explanation I have seen, Thank you very much!! I'm Subscribing
Anytime man!
It was very good one and easy to understand the problem . It helped a lot.
Nice, I'm glad!
thank you. Great explanation
You are welcome!
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
great content keep it up, buddy!
Awesome explanation. Thank you
Glad it was helpful!
Accurate explanation...Thanks a lot
Thank you :)
visualization helps. thanks !
excellent animation easy understanding very welll....
Awesome explanation bro
Thank you 🙂
Thanks for making videos with nice explanations.
Of course, thanks for watching
This was a great explanation! Thank you!
Glad you enjoyed it!
th-cam.com/users/maksrane100 check this too
Thank you this is so helpful!
Glad it was helpful!
I really like your explanations and that you code in Java.
Nice one. small doubt contains method not counted in big O ?
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
Thanks Man!!
Thank you for the video. I am simply curious about what is the underlying time complexity for function set.contains() and set.remove()
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).
Thank you.
Great explanation ! What software do you use to make these animation ? Thanks
u can use adobe premiere pro of filmora
@@زانغت_ساما thank you ❤️
When/where does the passed string s get placed inside hashset 'set'?
Wish you could build 424. Longest Repeating Character Replacement problem with the same approach you described here.
Thanks!
amazing explanation . thankyou so much:)
Anytime!
Great video.
Thanks
Subscribed!
set are not index based in cpp, any idea how to implement this in cpp?
Hi
Instead of creating a set for storing elements
We can create an character array?
Technically yes, but a set is better because the lookup with be O(1).
cool explanation
Glad it was helpful!
what would be the difference between set.size for max and i - j + 1 ?? why not just if statement if max is smaller than set.size then update max?
Wonder why you need the inner while loop, I thought hashset wouldn't have a duplicate so no need to remove within a loop.
8 th line While(set.contains(c)) in a set[p ] is there conduction true
Do you need the second while loop? Just the if(set.contains(c)) is sufficient right?
That's right. You can just remove the jth element and increment j in the else block, should work.