Minimum Window Substring | Google | Leetcode 76
ฝัง
- เผยแพร่เมื่อ 8 ก.ย. 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 TH-cam for recommending this to me 🔥🔥
Now i only search in this channel for any problem. This is a rare gold mine
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 ❤️
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 🙌🙌
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
wow an excellent teaching method love it
liked ur flow in the vedio and the way of teaching is great.Thanks
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
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
Bhai aap kamal ke ho....kya explanation dete ho yrrr...gajab
A good teacher can make everything simple and joyful ✨ Thankyou so much sirr❤ you ended the fear of hard problems✨
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.
Again best Explaination Thanku bhya 🥰
Had to watch twice but explanation was superb as always with each minute details and understood the whole story clearly
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))
Soothing voice+great explanation=🔥
Means a lot. Thank you so much 😇❤️🙏
This is nothing but a MASTERPIECE 🔥
Thank You sir ☺️
Glad i could help ❤️
Explanation : 3:00
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
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
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 please make a video on minimum window subsequence.Thank you.
Nice explanation SIRJI.
Meri jaan mja aa gya solution mai..kya mast smjhahya hai
Top Tier explanation jod>>>
Thanks a lot ❤️😇
very nice
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 🙏🙏❤️❤️
Excellent sir
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.
Thank you !
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. ❤
Thankyou for this amazing explanation.
awesome dude!! couldn't think it in first go.. how long did it took to devise this soln urself?
Salute hai bhai aapko😎
nice qn and good explaination
Understood.
thnx
Nice explanation!
Glad it was helpful! 😇
Thank You Sir .
Maja agyaa bro🔥🔥
Thank you ❤️😇
wow sir so nice explanation
nicely explained!
Glad it was helpful! ❤️🙏😇
🙏🙏🙏🙏
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
Thank you so much bro 🥰
Thank you so much
I am glad it helped 😇❤️🙏
This solution was showing TLE in GFG so it got optimized by using array...
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??
Its a beautiful explaination but the logic is tough to take in
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
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
❤❤
Bro what does that INT_MAX does i didnt get the last return part what are we actually checking can someone please help me
❤️❤️
❤❤❤
mazhar bhai biryani khaoge btao??? #GODOFDSA
❤
bhaiya amazing ,aapka linkedin ?
Thank you 😇
www.linkedin.com/in/mazhar-imam-khan-95a34ab3?
Can i take queue instead of deque
how to do these type of question without watching tutorial ??
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
//th-cam.com/video/3Bp3OVD1EGc/w-d-xo.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
Java solution ??
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);
🎉❤
Between D and B put D. And ur logic will not work as count vl be 1
me after watching this explanation " Swad++ "😂
Explanation ka BHAGWAAN HE YE
I am glad my channel is helping ❤️😇🙏