L12. Minimum Window Substring | 2 Pointers and Sliding Window Playlist
HTML-код
- Опубликовано: 25 мар 2024
- Notes/Codes/Problem links under step 10 of A2Z DSA Course: takeuforward.org/strivers-a2z...
Entire playlist: • Two Pointer and Slidin...
Follow us on our other social media handles: linktr.ee/takeuforward
![NoCap - Yacht Party [Official Music Video]](http://i.ytimg.com/vi/rm_lvDln8kE/mqdefault.jpg)
There was a slight mistake in the video.
1]. l++ in the while(cnt==m).
2]. It should be mp[s[l]]++; instead of mp[s[l]]--; in while(cnt==m) loop.
string minWindow(string s, string t) {
int l = 0, r=0;
int n = s.size(), m = t.size();
int cnt = 0, minLen = 1e7;
int startInd = -1;
mapmp;
for(int i=0;i
Yep I noticed this too 😊
s.substr(startind,strtind+minLen)
@@rkraj3339 no this is wrong
Yes
I think there are two points of Correction, that must have been missed :
1. hash[s[l]]++ as we are removing it while shrinking the string len.
2. we need to increment the l pointer at the end of the while loop where while(count == m).
Striver did a great job!
Thanks
yeah u are right
can you please paste the code here
@@tharungr7701 here you go
string minWindow(string s, string t) {
int n=s.size(),m=t.size();
map mp;
int l{},r{},cnt{};
int len{1000000009},idx=-1;
for(int i=0;i0) cnt--;
if(r-l+1
@@tharungr7701 string minWindow(string s, string t) {
string result;
if(s.empty() || t.empty())
{
return result;
}
unordered_map hash;
for(int i = 0 ; i < t.size(); i++)
{
hash[t[i]]++;
}
int minlen = INT_MAX;
int count = 0 ;
int sindex = 0 ;
int r = 0 , l = 0 ;
while(r < s.size())
{
if(hash[s[r]] > 0 )
{
count++;
}
hash[s[r]]--;
while(count == t.size())
{
if(r- l +1 < minlen)
{
minlen = r-l+1;
sindex = l;
}
hash[s[l]]++;
if(hash[s[l]] > 0 ) {
count = count -1;
}
l++;
}
r = r + 1;
}
return minlen ==INT_MAX ? "": s.substr(sindex , minlen);
@@tharungr7701 class Solution {
public:
string minWindow(string s, string t) {
int n = s.length();
int m = t.length();
if (m > n) {
return "";
}
int minLength = INT_MAX;
int sIndex = -1;
map mp;
for (int i = 0; i < m; i++) {
mp[t[i]]++;
}
int l = 0, r = 0;
int cnt = 0;
while (r < n) {
if (mp[s[r]] > 0) {
cnt++;
}
mp[s[r]]--;
while (cnt == m) {
if (r - l + 1 < minLength) {
minLength = r - l + 1;
sIndex = l;
}
mp[s[l]]++;
if (mp[s[l]] > 0) {
cnt--;
}
l++;
}
r++;
}
return sIndex == -1 ? "" : s.substr(sIndex, minLength);
}
};
Thank you striver for the awesome playlist🎉🎉🎉🎉
In the optimal approach there was a slight mistake, inside the nested loop it should be hash[s[l]]++ instead of hash[s[l]]-- and after the check for if(hash[s[l]]>0)cnt--; , a line needs to be added for l++; to shrink the window
c++ updated code -
class Solution {
public:
string minWindow(string s, string t) {
if (s.empty() || t.empty()) {
return "";
}
vectorhash(256,0);
int l=0,r=0,minlen=INT_MAX,sind=-1,cnt=0;
int n=s.size(),m=t.size();
for(int i=0;i
Hey can anyone tell me where is the mistake in my code its not passing all test cases.
class Solution {
public String minWindow(String s, String t) {
char[] hash = new char[256];
for (int i = 0; i < t.length(); i++)
hash[t.charAt(i)] += 1;
int l = 0, r = 0, sIndex = -1, minlen = Integer.MAX_VALUE, count = 0;
while (r < s.length()) {
if (hash[s.charAt(r)] > 0)
count++;
hash[s.charAt(r)] -= 1;
while (count == t.length()) {
if (r - l + 1 < minlen) {
minlen = r - l + 1;
sIndex = l;
}
hash[s.charAt(l)] += 1;
if (hash[s.charAt(l)] > 0)
count--;
l++;
}
r++;
}
if (sIndex != -1)
return s.substring(sIndex, sIndex + minlen);
return "";
}
}
thank you bhaii
@@MayankPareek facing the same error in java.
@@mohitthakur5904 take integer array instead of char array
@@MayankPareek While initializing the hash you should use : int[] hash = new int[256];
Was there any reason why you chose to do a: char[] hash = new char[256];
BTW! LOVED THE NEW WEBSITE INTERFACE.............MORE POWER AND SUCCESS TO YOU STRIVER AND HIS TEAM.
i am not able to login, are you able to?
@@ansulluharuka9243 yes! but i think there still some work is being done, so that may have caused u some problem in login, BUT let me tell you it's wind in there.
@@ansulluharuka9243 same here
same@@ansulluharuka9243
@@ansulluharuka9243 Same broo
completed this playlist today 27-05-2024
thanks striver!!
The new website is just amazing! I don't have words to say!!!!!! AMAZING!🤩🤩🤩and all of that for free!
Best Playlist on Sliding Window. Thanks Striver !!
recursion ki new playlist bhi le aao
( JAVA ) :----
class Solution {
public String minWindow(String s, String t) {
int l=0;
int r=0;
HashMap mpp=new HashMap();
int cnt=0;
int sindex=-1;
int minlen=Integer.MAX_VALUE;
String st="";
for(int i=0;i
Aur kitne playlist chahie recursion ke tujhe bhai?
thank you striver for this amazing playlist !!
Amazing work, Striver! You guys are really doing a great job for us by providing such a brilliant DSA course for free. It's genuinely useful for me. Please upload videos on strings in Striver's A2Z DSA Course/Sheet.......😇
Have completed sliding window playlist. Learned many things. Thank you so much...
loved this sliding window playlist ♥
Master of consistency🎉
Thanks Striver. Will always be grateful to you big brother
Hi striver , best series in the whole world and can you please bring playlist on basics of string
it should be hash[s[left]]++
also left++
can you please paste the code here
Completed this whole playlist in a single day. Thanks Striver for this. The way you teach makes me sit for long, think and implement and gradually the concepts start getting crystal clear.
like all of the 283? videos
@@Lm-mu1up lmao
@@lakshsinghania Hey ! Is sequence of this playlist proper and completed ?
@@Tushar_995 yeah it is, u can blindly follow it just the last qs which is given in the A2Z sheet is not covered here, otherwise good to go
@@lakshsinghania Ok ! I was thinking to start DSA but was confused between a LOT of channels and paid courses
Hey Striver,
I watch all of your videos and love the way you explain things. I am stuck on a problem called Josephus Problem from a quite long time. Please make a video on it.
Thank you you are so much hard working keep doing we have less good resources to learn like you
Understood...Thank You So Much for this wonderful video...🙏🙏🙏
New website is very good.... Nice work sir;🎉
Completed the playlist within a day. Sliding window is usually an easier topic as it is totally intuition based, but to identify the patterns and making a structure for all the solutions, you made it look like piece of a cake. Thanks Striver
Why do we store the starting index in brute foce approach ? Can you please explain it to me?
@@captain-ne8qy in the question we have to return our resultant substring right? So here we are iterating and all. Everything is fine but to return the substring, what do we want .....the first index of the substring, that is from where the substring is starting and the size so that we can calculate at what index the substring is ending, that's why we are storing both the starting index and size of the substring
Thnqu for the explanation!
Thankyou so much Striver for all you efforts throughout in delivering us so much valuable content. Any student / working professional can now be able to transition their career without paying money for courses.
Would also like your insights on the point :
While preparing for interviews most of the aspirants are going through the videos solely and solving the question after completely watching the video. And also are feeling lazy trying to solve the question on our own. What is the best way to complete any topic without being lazy and how should an aspirant approach any topic/playlist?
MUCH MUCH MUCH love for your efforts @Striver, the new Website UI Rocks!! Also, can you please tell the ETA for string playlist? I'm really holding on from watching others' videos just so that I can follow yours ;)
Thanks a ton🎉🎉
Understood brother. Thank you so much.
Bro's the 🐐
I enjoy grasping from your videos StriverBhai !! I wanted to highlight one mistake in code that inside while(cnt==m) you did hash[s[l]]-- but it should be hash[s[l]]++ as the condition is if(hash[s[l]]>0) cnt--; and you forgot to write l++ as well.
NOTE : MISTAKE in video ⚠⚠⚠⚠⚠⚠
here is the correct code :
class Solution {
public:
string minWindow(string s, string t) {
unordered_map freq;
for(char c : t) {
freq[c]++;
}
int l = 0, r = 0, minLen = INT_MAX, si = -1, cnt = 0;
while(r < s.size()) {
if(freq[s[r]] > 0) cnt++;
freq[s[r]]--;
while(cnt == t.size()) {
if(r - l + 1 < minLen) {
minLen = r - l + 1;
si = l;
}
freq[s[l]]++;
if(freq[s[l]] > 0) cnt--;
l++;
}
r++;
}
return si == -1 ? "" : s.substr(si, minLen);
}
};
Make playlist on CP problems for each algorithms atleast 30 each topic from 1200 div to 1800div
CP SHEET of yours has very less problems except for dp and math 😢
CODE IN C++
class Solution {
public:
string minWindow(string s, string t) {
unordered_map mpp;
int l=0,r=0,c=0,m=t.size(),index,minlen=INT_MAX;
for(int i=0;i
i lost all my progress with the new website update, when i logged in it again and marked my progress i lost it again and it says unautorized . The old website ui was much user friendly and better . The new update just made it more complex to navigate
yeah i also lost my progress data
sign out and sign in again and refresh the page
you can view ur notes under saved notes
++, lost all data, and new website doesnt save data, keeps reseting.
CPP code (Striver style):
class Solution {
public:
string minWindow(string s, string t) {
vector hashmap(256, 0);
int L=0,R=0, minlen=INT_MAX, start=-1, cnt=0;
for(int i=0;i0)
cnt = cnt - 1;
++L;
}
R++;
}
return start==-1? "":s.substr(start, minlen);
}
};
thankyou so so much sir
Day 2 of asking
Hey Striver,
When can we expect solution videos for Strings, Stack and Queues, few Recursion videos
as these are on top of queue, for A to Z sheet everyone needs them
Love your content and teaching methods
way from Brute to Optimum teaches us alot
I think there is slight correction in the pseudocode, I made these corrections while doing the problem I am posting it here ya'll can refer to it if you are facing problem, "
map mp;
for(int i=0;i
Impressed
Nice video, good learning, but can u cover sliding window plus binary search coding question
class Solution {
public:
string minWindow(string s, string t) {
if (s.empty() || t.empty()) {
return "";
}
vectorhash(256,0);
int l=0,r=0,minlen=INT_MAX,sind=-1,cnt=0;
int n=s.size(),m=t.size();
for(int i=0;i
class Solution {
public:
string func(string s, string t){
int n = s.size(), m = t.size();
int i = 0, j = 0, startindx = -1, minlen = INT_MAX, cnt = 0;
map freq;
for(auto a : t){
freq[a]++;
}
while(j < n){
if(freq[s[j]] > 0){
cnt++;
}
freq[s[j]]--;
while(cnt == m){
if(j - i + 1 < minlen){
minlen = j - i + 1;
startindx = i;
}
freq[s[i]]++;
if(freq[s[i]] > 0){
cnt -= 1;
}
i++;
}
j++;
}
cout
Bhayy... Please do more videos on this playlist.
when we are using the left iterator to pop the letter out, shouldn't we use "hash[s[left]]++" to increase the frequency of that letter in the hashmap instead and also add a "left++" after it to keep the "shrinking" going?
Understood better here Then Apna college channel
hey Striver ,you forgot to increment the l pointer and also in hash[s.charAt(l)]--; it should decrese the number but the value is increasing (example for d -> -2 if we perform hash[s.charAt(l)]--; (-2-1 => -3) so it should be hash[s.charAt(l)]++; (-2+1 => -1)
thanks for the amazing Playlist.
if anyone needs corrected code
string minWindow(string s, string t) {
int right=0, left=0, n = s.size();
map mp;
for(auto i : t){
mp[i]++;
}
int minLen = INT_MAX;
int startInd = -1;
int cnt = 0;
int m = t.size();
while(right0) cnt++;
mp[s[right]]--;
while(cnt==m){
if(minLen>right-left+1){
minLen = right-left+1;
startInd = left;
}
mp[s[left]]++;
if(mp[s[left]]>0) cnt--;
left++;
}
right++;
}
if(startInd==-1) return "";
return s.substr(startInd,minLen);
}
GOAT
Pro 🔥
Op...mind blowing algorithm
Stacks And Ques Ki Playlist Lao Bhaiya Pls
last question video of two pointer and string playlist, drop it soon please
understood
24:40 it should be hash[s[l]]++;
l++;
Please make a playlist on Heaps and Priority Queue Sir.
Since Placement session is going too start requesting you to please upload it soon.
Please Sir.
striver when will you upload videos on strings in AtoZ dsa playlist,please upload the video
What a playlist , Amazing Thanks Striver
Hey Striver, Its been 40 days. Please upload recursion patten wise video first . because recursion is required in advance topic like DP and graphs. So if we have recursion playlist complete we can go to DP and graph with confidence
bhaii tu toh wo nakli binod tharu hai na😂😂......videos bnana chhodh diya kya bhaii??
@@anmolbansal4009 yes right now , I have a job in Infosys.
@@MayankPareek ache videos bnata tha bhaii.....main dekhta tha tere videos.....band kyu krde....dobara shuru kr bhai bnana videos
Hey can anyone tell me where is the mistake in my code its not passing all test cases.
class Solution {
public String minWindow(String s, String t) {
char[] hash = new char[256];
for (int i = 0; i < t.length(); i++)
hash[t.charAt(i)] += 1;
int l = 0, r = 0, sIndex = -1, minlen = Integer.MAX_VALUE, count = 0;
while (r < s.length()) {
if (hash[s.charAt(r)] > 0)
count++;
hash[s.charAt(r)] -= 1;
while (count == t.length()) {
if (r - l + 1 < minlen) {
minlen = r - l + 1;
sIndex = l;
}
hash[s.charAt(l)] += 1;
if (hash[s.charAt(l)] > 0)
count--;
l++;
}
r++;
}
if (sIndex != -1)
return s.substring(sIndex, sIndex + minlen);
return "";
}
}
take Integer array instead of CharArray
@@aspirant8409 thanks brother
bhaiya recursion aur greedy ki bhi ek playlist bana do pls
Hello , striver , in your dsa a-z course , in step 17 and 18, tries and strings some videos are missing , will be soon said , would these videos come ?
Done
bhaiya , plz upload remaining topics like strings , stack nd queue plzz
pls post java collections vidoes
it will be very usefull for the people who are solving the problems in java
Please put separate solution videos for all the graph questions
thanks striver for this problem statement
here is the optimal solution with comments that will help me and you when we do revision for this type of question
class Solution {
public:
string minWindow(string s, string t) {
// if(s == t) return s; // if the both strings are equal then we dont have to go down;
int cnt = 0;
int minLen = INT_MAX;
int l= 0;
int r =0;
int n = s.size();
int index = 0;
//creating the hash map to keep therecord of the value
unordered_map mpp;
for(int i =0 ; i< t.size(); i++){
mpp[t[i]]++; //making flags so that they will help us for the count;
}
while(r= 0){
cnt ++;
}
//making the condition for the count
while(cnt == t.size()){
//setting the index according the min length
if(r-l+1 < minLen){
index = l; //then you update the index;
}
//first we get the current length and compaire it with our minLen
minLen = min( minLen, r-l+1);
//now we try to shrink the substring therefore we move l++;
mpp[s[l]]++;
if(mpp[s[l]] == 1){
cnt = cnt-1;
}
l++;
}
//after shirinking we need to extend
r++;
}
//if wwe want to send "" string as an output
if(minLen == INT_MAX) return "";
//getting the stirng by the size minLen // index to minLen; wala part
return s.substr(index, minLen);
}
};
keep liking this comment so youtube will notify me about this imp question :) :)
Would you please make a videos on strings 😊😊😊
prefix sum playlist too. Please sird
video me konsa whiteboard use kiya hai ?
Hello Striver,
the menu bar does no longer contain a link to tree Series in sub Category "DSA playlist". i was actually near to completion with only four questions left when the website suddenly updated could you please add the category again . thank you followed your playlist to the end.
"A problem in website in takeuforward."
1 Question remains from the sheet, Completed on 26/05/2024 (10:58 PM)
Can u give me a code snippet ..
Hey Striver, I know you have very busy schedule but please drop playlist quicker. Because I started Binary tree as all other playlist before it was completed. But on the hard question it require proper knowledge of Queue and Stack , Priority Queue. Which is not completed in the playlist. So learning became difficult. Hope you understand.
Bro i have a doubt if the hash[s[left]]-- then the character to be inserted to the hash right but hash[s[left]] to be incremented to reduce the value if it is positive then count should be decremented please resolve my doubt bro
Hey man can you upload the solution for minimum window subsequence also ?
some issue occurs in your website take you forward when i click mark option page says unauthorised please solve it ..
string playlist when
GFG links are back guys!!!
Anyone else is having issues with the new website? I am seeing unauthorized. As soon as I sign it is all fine but when I go to A2Z sheet or any section of the website it says that Unauthorized. Why is it happening
did u get the solution to correct it?
Bhaiya please upload video in A2Z playlist because you only hope for me
🔥🔥🔥🔥🔥
Please update string videos 😥
sir can u please start strings
i m a second year student and any test i give it asks for string dsa to be solved
Having trouble in accessing the website, the progress is not getting updated, it shows "Unauthorized" error message
Hey Striver, I am unable to login to the AtoZ dsa sheet after you updated it. Logged in through google earlier. Could you please check?
Same issue with me
when we click on open in new tab (video)both videos started and sounds mixed together .....so may be we can inhace this loop hole of new website master
Where to get class notes
Anyone completed the playlist anything that is missing?
A minor mistake at 24:28 -- it would be "hash[s[L]]++;"
I am unable to login with my google account after update
Why is the backend down??
we need stringsssss
In the first approach, the nested for loop should be from j=i to n instead of j=0 to n, because we are checking for each substring
DOES ANYBODY THINKS THE SAME ?
Bhai dsa retain nhi hota brain me imagine karna me problem hota hai koi solution btaye
can some one tell why it's coming unauthrized when ever i open sde sheet in browser. The issue is been from many days
Bss Ab STRINGS ki playlist le aao bhaiya please !
bhaiya new series kab? squat champ is waiting
what u did to TFU website man , crashing a lot ..
some login issue and token refresh not happening properly looks like
But good UI , just fix login issues ...
Bhaiya i faced some issues with new website, can you please fix it 🙏🙏. Every time i tried to read about the topic it shows unauthorised
bhaiya website update hone ke baad jab koi bhi topic ke article kholte hai to undefined tutorial likha ata hai....The articles are not opening.If possible please resolve this issue as soon as possible.It will be a great help.Thank you.....
In the Brute Force Solution 'j' should be start from 'i', rather than '0'.
Bit Manipulation series over?
website solution link not working