Minimum Window Substring | Google | Leetcode 76
HTML-код
- Опубликовано: 26 авг 2024
- This is the 5th Video of our Sliding Window Playlist. This is one of the best Qns on Sliding Window and hence the most popular one.
The interesting Problem is - "Minimum Window Substring" | Leetcode 76
We will do live coding after explanation and see if we are able to pass all the test cases.
Problem Name : Minimum Window Substring | Leetcode 76
Company Tags : Google, Amazon, Microsoft, Codenation, FactSet, , Atlassian, MakeMyTrip, Streamoid Technologies, Media.net, Airbnb
My solutions on Github(C++ & JAVA) : github.com/MAZ...
Leetcode Link : leetcode.com/p...
GfG Link : practice.geeks...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My GitHub Repo for interview preparation : github.com/MAZ...
Subscribe to my channel : / @codestorywithmik
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
✨ Timelines✨
00:00 - Introduction
#codestorywithMIK
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #2024 #newyear #RecursionExplained #CodingJourney #Programming101 #TechTalks #AlgorithmMastery #Recursion #Programming #Algorithm #Code #ComputerScience #SoftwareDevelopment #CodingTips #RecursiveFunctions #TechExplained #ProgrammingConcepts #CodeTutorial #LearnToCode #TechEducation #DeveloperCommunity #RecursiveThinking #ProgrammingLogic #ProblemSolving #AlgorithmDesign #CSEducation
Hope whoever search this question , yt recommend your solution so everyone can come to know this masterpiece, amazing , wonderful solution that you have created. Truly amazing way of explaining thanks dude to help us out in such a easy way .
Wish you infinite success ❤
Thank you so much 😇❤️
I have pinned your comment so that others could see ❤️❤️
Thanks to RUclips for recommending this to me 🔥🔥
Now i only search in this channel for any problem. This is a rare gold mine
Awesome Mazhar bhaiyan, I have seen video solution on the two very famous DSA channel but according to me, your explanation beats their explanation in terms of making others to understand it, which makes you stand out from crowd & put you into very great teacher of DSA of Asia continent! Hats off to you 🙌🙌
This dude is a gem. The effort you put in while explaining is amazing. The most hardworking dry run ever seen in a channel.
Thank you so much ❤️
Let me say this, not every youtuber does a code along. Appreciate it sir. You have calming voice which makes understanding of problem much better XDDD. Plus you dont try to teach in english(Hindi all the way). THANKSSSS A LOTT. please dont stop making videos.
Just a suggestion please discuss the time complexities also and hints of alternative solutions
Feedback taken Mridul. Thanks a lot for your precious words.
After searching this problem, when i saw you made a video on this, my eyes lit up😊
Thank you so much ❤️❤️❤️
Best explanation on youtube
I have watched multiple youtube videos before coming here and didn't understand. I was about to give up that its not my cup of tea. Now your explanation made my day.
Bhai maja aa gaya. Thanks itna achcha video banane ke liye.
Never ever give up ❤️❤️❤️
This is GOLD. Best explanation over internet.
Hey bro
You are the best explainer
Please keep it up
Mai to fan ho gya aapka
Hi sir, can you please make a video on the LC 727 Minimum Window Subsequence (premium) / GFG version of it? Your explanations are amazing and I am struggling to solve that problem sir
Explanation : 3:00
Couldn't solve it even after seeing other youtuber's explanation but after seeing your explanation I could solve it easily
🙏🙏❤️❤️ so glad to hear this
@@codestorywithMIK 🙏
awesome brother
wow an excellent teaching method love it
Bhai aap kamal ke ho....kya explanation dete ho yrrr...gajab
liked ur flow in the vedio and the way of teaching is great.Thanks
A good teacher can make everything simple and joyful ✨ Thankyou so much sirr❤ you ended the fear of hard problems✨
bhaiya boht acha explaint kiya hai, bs TC aur SC bhi bta dete toh maza a jaata 🙂🙂
TC -> O(m+n)
SC-> O(m+n) , because map will store characters of both strings
To reduce space complexity you can only store characters of t in map.
While iterating through the characters of s string you have to check whether the key exist in map or not
(But TC of finding key exist or not is O(log n))
Excellent explanation my brother thank you so much
❤️❤️❤️
Thank you boss i just watched 20 min of your viideo and then solved it on my own.
Had to watch twice but explanation was superb as always with each minute details and understood the whole story clearly
Soothing voice+great explanation=🔥
Means a lot. Thank you so much 😇❤️🙏
Again best Explaination Thanku bhya 🥰
This is nothing but a MASTERPIECE 🔥
Thank You sir ☺️
Glad i could help ❤️
Top Tier explanation jod>>>
Thanks a lot ❤️😇
Meri jaan mja aa gya solution mai..kya mast smjhahya hai
Really hard made easy by your explanation… 😊😅❤please continue ❤
Thank you so much ❤️😇🙏
@@codestorywithMIK could you please cover leetcode 726 - no of atoms problem... please
Thank You Sir .
I also have another approach wehre instead you have counter make the the use of another array and keep adding characters until the m1 == target_map and if becomes equal try to remove the characters.
Awesome Sidharth. ❤️❤️
Thanks a lot for sharing your idea.
Would you also please share the code
Sir please make a video on minimum window subsequence.Thank you.
Nice explanation SIRJI.
Ek cheez please bta dijiye, if abc ki aabc hota in which a is repeating toh count characters wala jo variable hai uski length 4 hi jaati ya 3 jaati since unique characters sirf 3 hai
Uski length 4 Jaati. Kyoki hume poori string 't' chase in 's' . 't' ki length 4 hai to poori 4 length Jaati. I hope I could answer your qn.
Thanks a lot again for your comments. ❤
Amazing explanation. Thank you very much.
I have a question - why did we kept track of frequencies of all characters (which are not in t string)? Don't we just need the characters in t string? I was just curious.
Yes ur Right, I thought the same way, coz storing the unwanted characters in the map also can increase space complexity and make code large.
very nice
Excellent sir
thank you for the optimised approach , i came up with this :
class Solution {
public:
bool isEqual(vector &window){
for(int i = 0; i < 128; i++){
if (window[i] > 0){
return false;
}
}
return true;
}
string minWindow(string s, string t) {
if (s.size() < t.size()) return "";
vector count(128,0);
for(auto &ch : t){
count[ch]++;
}
string ans = "";
int start = 0, end = 0, minSize = INT_MAX;
while(end < s.size()){
//update curr element
count[s[end]]--;
//shrink window
while(count[ s[start] ] < 0 && start < size(s)){
count[s[start++]]++;
}
//update valid window to ans
if(end-start+1 < minSize && isEqual(count)){
ans = s.substr(start,end-start+1);
minSize = ans.size();
}
end++;
}
return ans;
}
};
*/
Sir how you are so much consistent... What do you do to be so focused...? Yoga, meditation or anything! I am surprised 🤯 sir. Please if you don't mind please share your routine with me. It would be helpful.
I’ll definitely make a video on that 🙏🙏❤️❤️
awesome dude!! couldn't think it in first go.. how long did it took to devise this soln urself?
Salute hai bhai aapko😎
thnx
Maja agyaa bro🔥🔥
Thank you ❤️😇
nice qn and good explaination
This solution was showing TLE in GFG so it got optimized by using array...
Thank you !
Understood.
Thankyou for this amazing explanation.
Nice explanation!
Glad it was helpful! 😇
Its a beautiful explaination but the logic is tough to take in
🙏🙏🙏🙏
wow sir so nice explanation
nicely explained!
Glad it was helpful! ❤️🙏😇
The same problem when I tried submitting on gfg using this solution gives TLE with 4000/5000 tc passed, please suggest me how can I optimise it more
complexity = O(n*2) ~ O(n) ? where n is length of s?
my thinking, every element gets added and deleted/not deleted in the sliding window
so for every n, at worst we have 2 operations
Thank you so much bro 🥰
Thank you so much
I am glad it helped 😇❤️🙏
insane explanation
Java program
class Solution {
public String minWindow(String s, String t) {
int n=s.length();
if(t.length()>n){
return "";
}
HashMap map=new HashMap();
for(char ch:t.toCharArray()){
map.put(ch,map.getOrDefault(ch,0)+1);
}
int required=t.length();
int i=0,j=0;
int minWindow=Integer.MAX_VALUE;
int start_i=0;
// exploring window
while(j0){
required--;
}
map.put(ch,map.getOrDefault(ch,0)-1);
while(required==0){
// shrinking window
int curr=j-i+1;
if(minWindow > curr){
minWindow=curr;
start_i=i;
}
char c=s.charAt(i);
map.put(c,map.getOrDefault(c,0)+1);
if(map.getOrDefault(c,0)>0){
required++;
}
i++;
}
j++;
}
return minWindow==Integer.MAX_VALUE? "" : s.substring(start_i,start_i+minWindow);
}
}
Done
Crystal clear explanation thanks a lot bhaiya ❤❤ but bhaiya problem leetcode pe to submit hogya but gfg pe kyu TLE mar gya 🥹
Thank you 😇❤️
Can you share gfg code that you are trying ?
@@codestorywithMIK Yes bhaiya sure, here it is
class Solution
{
public:
//Function to find the smallest window in the string s consisting
//of all the characters of string p.
string smallestWindow (string s, string t)
{
// Your code here
int n =s.length();
if(t.length()>n)return"";
unordered_mapmp;
for(char &ch:t){
mp[ch]++;
}
int requiredCount=t.length();
int i=0, j=0;
int minwindowSize =INT_MAX;
int start_i=0;
while(j0){
requiredCount--;
}
mp[ch]--;
while(requiredCount==0){
int curWindowSize = j-i+1;
if (minwindowSize>curWindowSize){
minwindowSize = curWindowSize;
start_i=i;
}
mp[s[i]]++;
if(mp[s[i]]>0){
requiredCount++;
}
i++;
}
j++;
}
return minwindowSize==INT_MAX?"":s.substr(start_i,minwindowSize);
}
};
@@codestorywithMIK any updates bhaiya??
❤❤
how to do these type of question without watching tutorial ??
Can i take queue instead of deque
Bro what does that INT_MAX does i didnt get the last return part what are we actually checking can someone please help me
bhaiya amazing ,aapka linkedin ?
Thank you 😇
www.linkedin.com/in/mazhar-imam-khan-95a34ab3?
def minWindow(self, s: str, t: str) -> str:
d={}
count=0
req_count=len(t)
n=len(s)
start=0
min_size=inf
for i in range(len(t)):
d[t[i]]=d.get(t[i],0)+1
i=0
for j in range(len(s)):
ch=s[j]
if ch in d and d[ch]>0:
req_count-=1
d[ch]=d.get(ch,0)-1
while(req_count==0):
# shrink
if j-i+1
Java solution ??
❤❤❤
❤
//ruclips.net/video/3Bp3OVD1EGc/видео.html
//we will use map on t to check if we need those letters or not,
//we will use the concept of sliding window
//we need to make user that all the eleemnts of t r present in s so we will use cound required that will be the length of the t
//ur i and j will be at the benginging, j will go forward if ur count required is >1
//ur i will move forward if ur count required
ye approach gfg pe tle mar rhi hai
public String minLength (String s,String t){
int[]cnt=new int[128];
int req=t.length(),left=-1,minLength=s.length()+1;
for(char c:t.toCharArray())
++cnt[c];
for(int l=0,r=0;r=0)
--req;
while(req==0){
if(r-l+10)
++req;
}
}
return left==-1?" ":s.substring(left,left+minLength);
}
tc=(m+n);m=t.length,n=s.length,
sc=(m);
🎉❤
me after watching this explanation " Swad++ "😂
Explanation ka BHAGWAAN HE YE
I am glad my channel is helping ❤️😇🙏
❤️❤️