In the beginning it looked like very difficult to me but after some I started getting it and at the end everything is clear. Thanks a lot bro 🔥🔥🔥🔥

We hope you will post more videos like this. Very valuable problems and solutions!

@codingatascale4927

4 жыл бұрын

Thanks for your feedback, I will have to get permission from my current employer first, I recently joined one of the FAANG companies and they have a specific policy around that.

Brilliant! Easy and clear!

Wow thanks for the video !! I kind of like coming up with name for techniques, I think "rebounding sliding window" would fit well for this one :D

thanks for covering all possibilities

Great solution, really we appreciate what you do

Thanks for sharing. Great explanation!!!

awesome ! easy to follow!

what if bring the i pointer directly to end -1instead of i++ (just calculate the the end-i

Thanks alot , very easy explained

At first look I thought it will be tricky one. But everything was streght and forward. Thank you for your explaination. Don't loose your motivation. Best of luck! The time complexity will be O(NxM) (N is S length and M is T length)

Beautiful approach !!

Perfect explanation.

Excellent Solution !

Btw, can you please do a video on Minimum window substring if its possible?

I was so confused, crying my eyes out at my own stupidity, and then I found this video and I felt stupid no more, thank you habibi

@nosouponhead

3 жыл бұрын

Actually crying?

@megamind9175

3 жыл бұрын

@@nosouponhead leetcode make me cry, it is true

@himzp

3 жыл бұрын

solution here is so simple, that it made me cry more :D

This is a nice intuitive solution, I was wondering if there is a way to do this in O(S+T)?

@codingatascale4927

3 жыл бұрын

I don’t think so

Damnnn you made it simple thanks

This is awesome

Very nice explained

Super Awesome trick.

Great Approach

very good explanation.

OMG this is sssooo smart !!!

Aamazing

Hello, I try to write a python code for your solution. But It has bug. Coud you help me to find it? Let's me know thank you

@aunnfriends

3 жыл бұрын

class Solution: """ @param S: a string @param T: a string @return: the minimum substring of S """ def minWindow(self, S, T): window = "" i, j , min_l = 0, 0, len(S) + 1 while i if S[i] == T[j]: j += 1 if j == len(T): end = i + 1 j -= 1 while j >= 0: if S[i] == T[j]: j -= 1 i -= 1 j += 1 i += 1 if end - i min_l = end - i window = S[i:end] i += 1 return window

@rish2025

3 жыл бұрын

Don't try to write a For loop in python and change the value of the iterator. The iterator will move back to its original value in the next iteration of the loop and you will not be able to traverse back.

awesome explanation! What are the complexities and why?

it'd be nice to have an explanation on the time complexity

thankyou sir ,you are grate..

thats gangsta

amazing explanation

Can you please tell us the time complexity of this solution?

@MohamedShehab

3 жыл бұрын

Worst case O(ST) , best case O(S+T) So O(ST)

@MohamedShehab

3 жыл бұрын

Worst case when you have a string like this: “aaaaaaaaaaaaaaaaa” and you’re looking for “aaa” for example

I am assuming it is O(2ST) which comes down to O(ST). Please correct me if I am wrong. Thanks!

@deepakanuraagsathyanarayan9666

4 жыл бұрын

it should be O(S+T) right - one forward pass of S one backward pass of T

@codingatascale4927

4 жыл бұрын

Worst case yes O(S*T)

@hqdevelopers3697

4 жыл бұрын

@@deepakanuraagsathyanarayan9666 I agree with you: O(S+T)

@ljkb23

4 жыл бұрын

It is O(ST) because it is O(T+(# of pattern found)*S) which in worse case O(ST).

slight modification do not store substrings again and again store starting index and length and find substring at the end

Ohh my god what an explanation 😃😃😃😃😃😃😃😃

why you`ve stopped making such amazing videos

What is the time complexity of your approach

@codingatascale4927

3 жыл бұрын

O(ST) at worst

I wish you could explain point out the time complexity at the end of the explanation.

Wouldn't the algorithm fail if S = XAYMBAZBDCEABE and T = ABE? The answer is ABE but since you stop at the first occurrence of E, you would output AZBDCE.

@codingatascale4927

5 жыл бұрын

Hi Abischek, It'll actually output ABE. If you check the algorithm you'll find that it doesn't stop with the first match, but rather continues to find more. Here's a gist if you'd like to try it by yourself: gist.github.com/shehabic/52ccbf4bb23795ae31b65566016c434f

@xiaoxiaozhang3924

5 жыл бұрын

That is what I thought. So this solution is not right.

@codingatascale4927

5 жыл бұрын

@@xiaoxiaozhang3924 every time you find a solution you go back and count the length, and since you reset the pointer of T, you continue looking for the next occurrence, so indeed it doesn't stop until it finds all possible solutions and the shortest ones to be specific. Here's the sample with the example above. gist.github.com/shehabic/52ccbf4bb23795ae31b65566016c434f

@jayanthavasarala

4 жыл бұрын

Hi Party

@AbhishekRaj-ew1zp

4 жыл бұрын

@@jayanthavasarala Arey Paaaaaarty. Kaisa hai yaaro? Small world. Let's catch up sometime.

I found the bug. For loop in python is different in Java.

@rish2025

3 жыл бұрын

Yeah. Don't try to write a For loop in python and change the value of the iterator. The iterator will move back to its original value in the next iteration of the loop and you will not be able to traverse back.

Time : O(M * N) Space : O(1)

Seems wrong .. try ABE with AdjApdoBsjsEABE

@codingatascale4927

4 жыл бұрын

You can try it in the sample code on github

class Solution { public String minWindow(String s1, String s2) { int start =-1; int sIndex=0; int tIndex=0; int sLen = s1.length(); int len = sLen+1; while(sIndex if(s1.charAt(sIndex) == s2.charAt(tIndex)){ tIndex++; if(tIndex == s2.length()){//contract the window from right to left int end = sIndex + 1; tIndex--; while(tIndex >=0 ){ if(s1.charAt(sIndex) == s2.charAt(tIndex)){ tIndex--; } sIndex--; } //since j becomes negative tIndex++; sIndex++; if( end - sIndex len = end - sIndex ; start = sIndex; } } } sIndex++; } return start == -1 ? "" : s1.substring(start, start + len); } }

This is O(N^2) since after getting the first candidate you increment i by one and start searching for the next candidate.

@codingatascale4927

4 жыл бұрын

No, it’s O(s*t) in the worst case, where m is the subsequence

@codingatascale4927

4 жыл бұрын

You increment j by 1 from the shortest subsequence found not from the first i you started with

@anirudhravichandran6892

4 жыл бұрын

@@codingatascale4927 for every window you find, this is going to be O(S). the number of windows you can find is of the order O(S) as well, for example T="a" and S = "aaaa"

@tomwong3336

3 жыл бұрын

​@@anirudhravichandran6892 I agree with you. For example, this test case: S = XAYMBAZBDCEABE and T = ABE. Because when you get all the matching characters, you travel back to the last seen A and the length of this travel "AZBDCE" is longer than T, probably it's O(S). so, the time complexity for this algorithm is O(S*S) not O(S*T).

my converted Python code class Solution: def minWindow(self, S, T): window = "" i, j , min_l = 0, 0, len(S) + 1 while i if S[i] == T[j]: j += 1 if j == len(T): end = i + 1 j -= 1 while j >= 0: if S[i] == T[j]: j -= 1 i -= 1 j += 1 i += 1 if end - i min_l = end - i window = S[i:end] i += 1 return window

This explanation doesn't work for "abaacabcc" with substr "abc"

@codingatascale4927

Жыл бұрын

Works, the code is linked feel free though try it.

I think minWin = S,substring(end, i) should be minWin = S,substring(i, end + 1) because end will always be greater than i.

@codingatascale4927

2 жыл бұрын

I linked the code, feel free to try it

This solution is wrong. For S=AXBYESABE T = ABE Your code will return AXBYE. But the real answer is ABE

@MohamedShehab

Жыл бұрын

Code is attached, you can try it yourself

@chillrelax5056

Жыл бұрын

@@MohamedShehab Yeah it does. But you took the simplest possible example to do a walkthrough. I doubt you really understand the code. Or if you have just copied it from somewhere else.

@MohamedShehab

Жыл бұрын

@@chillrelax5056 interesting how you judge if I understand my code or not, whatever you say :), you can also find a full set of problems I solved shared on my github repo above.

@chillrelax5056

Жыл бұрын

@@MohamedShehab Hmm maybe you are right! I am preparing for interviews under pressure! so please ignore my comments. Peace!

@MohamedShehab

Жыл бұрын

@@chillrelax5056 no worries, best of luck in your upcoming interview, and hopefully you'll land the job. Peace!

i think wrong solution consider a case s="azbcabc" t = "abc" this solution will give answer "azbc" but right answer you know man just check

@codingatascale4927

10 ай бұрын

I linked the code on my github account, you can try it yourself, so many come here and say the solution doesn’t work, either without watching the full video or not trying the code.