Minimum Window Substring (Leetcode Hard) | Hashmap Interview Questions
Vložit
- čas přidán 8. 10. 2020
- Please consume this content on nados.pepcoding.com for a richer experience. It is necessary to solve the questions while watching videos, nados.pepcoding.com enables that.
NADOS also enables doubt support, career opportunities and contests besides free of charge content for learning. Here you will learn about Minimum Window Substring problem using hashmaps and 2 pointer approach. In this question :
1. You are given two strings s1 and s2 containing lowercase english alphabets.
2. You have to find the smallest substring of s1 that contains all the characters of s2.
3. If no such substring exists, print blank string("").
To attempt and submit this question, click here: www.pepcoding.com/resources/d...
For a better experience and more exercises, VISIT: www.pepcoding.com/resources/o...
Have a look at our result: www.pepcoding.com/placements
Follow us on our FB page: / pepcoding
Follow us on Instagram: / pepcoding
Follow us on LinkedIn: / pepcoding-education
sir, your explanation is damn perfect.
every time search for a coding solution, I wish I found pepcoding there.
Glad to know that you liked the content and thank you for appreciating.
The love and respect which I get from you people keep me highly motivated and the same I am able to forward It to you people through my videos.
So, keep motivating, keep learning and keep loving Pepcoding😊
@@Pepcoding yes sir
U r just awesome
Very Engaging and DETAILED explanation! I am naturally Extra Focused during his videos.
You explained this hard problem in such an easy way. Thankyou :)
Sir, you are the best🖤. Just understood the whole concept of the problem and approach within 6min. Great explanation
Great explanation. I was scratching my head whole day reading about this solution online.
Sir aap great ho sir. Mene ek course lia tha, uss course ne itna confuse kar dia ki khud pe doubt hone laga.Firr aapki dekhi tab jaake samjh aane laga.Ab waha se questions dekh ke explanation ke liye pepcoding pe aata hoon
you are the reason why i am getting interested in programming.
thank you
You make this problem is so easy for us. Thank you so much sir
Wow Sir !!! Mazaa hi aa gya kahin nahi mili t iski itni easy explanations .
Sir ji tussi Great ho .
Hard question and simple explaination, maza aa gya sir💯
thank you
Superb explanation!
Amazing explanation - this is an understatement!
I have seen a lot of video before landing here but you have given a very clear explanation .. great work man :)
Glad it was helpful!
Perfect explanation. Couldn't resist to comment
Brilliant explanation!! Thank you sir
sir you gave outstanding explanation with a simple code. love the way of your teaching
:)
Thanks a lot sir to make me understand this hard problem.
Sir, Your explanation is one of the greatest thank you so much.
Nice explanation sir.....thanks for making the video
your explanation is very easy for this hard question ,thanks sir
"Bina baat ki cheezien acquire ho rahi hai.." :D , bhai pareshaan ho gaya kuch dhang ka acquire nahi ho raha :D.
Best way of explaining, love your videos :)
I think no one can explain these tricky solutions better then you sir ......... : )
Thanks a lot, for better experience and well organised content sign up on nados.io and start learning.
we can return the string when releasing and the match (6) count is the same as the length of the substring (as its the best possible answer) ?
thanks bro, very good explanation. keep up the good work.
great explanation sir, thank you very much.
I understood in half way you make hard question so easy.Thank you sir you are doing great job👍.
I am glad you liked it. I also hope that you are watching till end and trying to understand the what, how and especially why of the problem.
If you like our efforts, we request a review - g.page/Pepcoding/review?rc
Thank you so much. You explained it very clearly. and subscribed too :)
Glad it was helpful! and If you like our efforts, please upvote the comments written by the students about Pepcoding here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
Awesome Explaination indeed !!!
Thank you so much sir!
you are a great teacher sir
Nice explanation!!
nice explanation after watching so many videos this video is so much helpfullllll........
Thankyou beta!
If you like our efforts, will you like to write a few words about us here (www.quora.com/How-do-I-start-learning-or-strengthen-my-knowledge-of-data-structures-and-algorithms )
Do not remove the character from map1 ,if suppose the frequency is zero in map2 then it will take the default frequency 0 in map1 also and while comparing it will not decrement the mcnt and second thing is getDefaultOrZero function is incrementing the value on first hit itself to 1 instead of zero in map1 so containsKey method should be used for checking if the character exists in map or not then increment the value in else condition if it exists.
the way you explain is superb..thanks
You are most welcome
Aap to bade heavy driver nikle
Really good explanation
superb explaination
best explaination❤
This was lit🔥
Hard Problems seems easy after your video, good job sir.
I am glad you liked it. I also hope that you are watching till end and trying to understand the what, how and especially why of the problem.
If you like our efforts, we request a review
g.page/Pepcoding/review?rc
You can subscribe to our channel here
czcams.com/users/Pepcodingabout?view_as=subscriber
Every time I see his video on a topic I'm learning I am like, okay it will be cleared I can plan for next one. He is God 🙏
This question seems simple but isn't. GG on explaining it!
haina!!
i got the logic before i saw the video, and i coded too, only few test cases were passing, i did a lot of dry run and modified my code, but still it was not working, in this case i should just follow the other approach and code?
easy to understand thank you sir
Sir, what is the space and time complexity of the solution?
you are amazing :)
The concept is very tricky and very useful for other problems as well. It gives a new perspective to solve a problem. Thank you :)
yes it is really an importent concept which can get used in lot of other problems:
If someone comment in future here I will get notify and I will revise this concept again
@@Kashish_Batra Lag gai
Thanku sir❤️❤️
Thank you sir
your explanation was so good that i build my own code 🙂
public static String minWindow(String s, String t) {
HashMap reqFreq = new HashMap();
int reqMatch = t.length();
for (char c : t.toCharArray()) reqFreq.put(c, reqFreq.getOrDefault(c, 0) + 1);
String ans = "";
HashMap workFreq = new HashMap();
int i = -1, j = -1, currMatch = 0;
while (i
nice explaination..but sir you dont need to substring it everytime as for large string it would drag your performance..you just need to store the start and end index
Awesome explanation! Seriously great, you keep us glued to the video till the end.
I had one ques what would be its time complexity?
Yes same question, what would be the time complexity?
O(n)
sir what is the time complexity for the above question?
We can also use array instead of hashmap..
Very Nice Explanation.......Keep making videos
Thankyou beta!
I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem.
If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
Thank you sir, for the content🤗... But one minor correction is required...While collecting the answers, the length will be i-j.......s1. substring(j+1, i-j)....
I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem.
If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
Your explanation is soo simple.
Thank you so much. Keep learning, Keep growing and keep loving Pepcoding!😊
Thankyou very much sir🙏
Most welcome
Best explanation ever
I am glad. Keep learning. Keep supporting. Your kind words are the kind of motivation that truly help me in making more and more content. Especially, these days, not everybody is generous with motivating anybody either. It means a lot
Kya explain Kiya h sir.. outstanding😊
Thankyou beta!
I am glad you liked it. I also hope that you are watching till the end and trying to understand the what, how, and especially why of the problem. If you like our efforts, will you like to write a few words about us here (www.quora.com/How-do-I-start-learning-or-strengthen-my-knowledge-of-data-structures-and-algorithms )
Sir, This will work with linear time complexity right ?
why we are doing minus i.e while i
otherwise it will throw string index out of bound exception...
Best explanation 🙏🙏🔥🔥
Glad you liked it
Just how do you convert your thinking to code so "Easily", it looks like a piece of cake to you, but I am unable to do it, even after knowing the way to do it.
Can't be better than this...No way...
watched till half and boom got the green tick! , thanks :-D
Keep learning and Keep supporting.
Will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms)
Done!
Loved ur explanation bhai
I am glad you liked it. I also hope that you are watching till end and trying to understand the what, how and especially why of the problem.
If you like our efforts, we request a review
g.page/Pepcoding/review?rc
You can subscribe to our channel here
czcams.com/users/Pepcodingabout?view_as=subscriber
Lovely explanation brother🙌🙌🔥🔥
jara submit kriyo ye code leetcode pe
Sir,You are best
wow, this cheers me up. I am glad we at pepcoding could be of help to you. Keep learning. Also, recommend us to your juniors and peers, they may also benefit.
Sir, honestly aap humari hopes ko alive rkhte ho.
wow, this cheers me up. I am glad we at pepcoding could be of help to you. Keep learning. Also, recommend us to your juniors and peers, they may also benefit.
what is the time complexity?
Very nice video. A complex algorithm looks so simple and easy to implement. Please post more videos.
Suggestion for next problem :
Similar problem, just a twist the substring should contain the characters in the same order as pattern.
If the solution is ready. Please send the link :)
Yes, sure
string matching algos then
C++ Concise. Easy to understand
string minimumWindowSubstring(string str, string target) {
int n = str.size();
map map;
for (char c : target)
++map[c];
int minLen = n + 1;
int count = 0;
int k = map.size();
string result = "";
int i = 0, j = 0;
while (j < n) {
if (count < k) {
if (map.count(str[j])) {
--map[str[j]];
if (map[str[j]] == 0)
++count;
}
++j;
}
while (count == k) {
if (minLen > j - i) {
minLen = j - i;
result = str.substr(i, j - i);
}
if (map.count(str[i])) {
++map[str[i]];
if (map[str[i]] == 1)
--count;
}
++i;
}
}
return result;
}
thanks this code was more understandable, I saw Aditya Verma Sir's SlidingWindow technique video but could'nt able to code it.Really thanks sir:)
tle aajayega
The explanation was really excellent when I saw this question I was confused much after watching your video It's crystal clear Thank You Sir
Glad it helped! For better experience and precisely arranged content visit on nados.io
Sir in this question what is an alternative version of map.getordefault in c++ ?
ek fn likhna hoga agar count zero hai to saamne frequency 1 daal dein. nahi to badha dein
Nice explanation. May I know what is the tool you used for explaining the algorithm. I really liked the Tool.
That is Open Board.
Time Complexity?
C++ Solution with a few tweaks
(1) -> Instead of storing ans as a string I stored its starting and ending index ( and length also for easy understanding)
because I think .substr() takes much higher time than just updating 2-3 variables.
GOOGLE SAYS-> substr(): Returns a string which is the copy of the substring. Its time complexity is O(N) where N is the size of the substring.
(2) -> Instead of making map for curr stage made a frequency vector
its size will be 58 => 26 capitals + 6 SPECIAL CHARACTERS IN BETWEEN + 26 small
and to get the index from character do : char - 'A'
SEE THE ASCII TABLE IF YOU DIDN'T GET THAT
my LEETCODE submitted ans:
class Solution {
public:
// two pointer acquire and release strategy
string minWindow(string s, string t) {
vector req(58,0); // char in t and there required frequency
for(char c: t){
req[c-'A']++;
}
vector curr(58,0); // freqency array (saves time than map) (26 + 26 +6 special char in between )
int r = -1; // right pointer to acquire
int l{-1}; // left pointer to release
int rmc = t.length(); // required match count
int cmc = 0; // current match count
int slen = s.length();
int anslen = 0;
int al{-1};
int ar{-1};
for(int r{}; r< slen; r++){
//acquire
char cc = s[r]; // current char
curr[cc-'A']++;
if(curr[cc-'A'] r-l){
anslen = r-l;
ar = r;
al = l;
}
l++;
char cc = s[l]; // current char
curr[cc-'A']--;
if(curr[cc-'A'] < req[cc-'A']){
cmc--;
}
}
}
string ans{""};
if(ar != -1){
ans = s.substr(al+1,ar-al);
}
return ans;
}
};
You saved a lot of my time, tnx
Im getting memory limit exceeded error, anyone can help?
exceeds time limit on leet code, for case 266
class Solution {
public:
string minWindow(string s, string t) {
string result = "";
/*step1 create a hash map of all characters in substring*/
unordered_map map2;
for(int k=0;k
This man is clearly underrated
Hope you love the explanation, for better experience and well organised content visit - nados.io
awesome work..
Thank you sir
bhai likh ke deta hu mene phle bhi comment kia he ye pep coding just java me he isliye audience kam ho jati he wrna sach bolta hu sumeet sir jesa thought process built krke padhana rare he.code to koi bhi likh kar explain kr de par dhang se zero se smjha pana har kisi ke bas ki bat nhi h ... SALUTE SIR APKO !!!
wow, this cheers me up. I am glad we at pepcoding could be of help to you. Keep learning. Also, recommend us to your juniors and peers, they may also benefit.
@@Pepcoding SURELY!!!
❤❤
Amazing explanation
Glad you think so!
If you like my efforts, I request a review
g.page/Pepcoding/review?rc
your explanation is very good but plz whenever you make videos please discuss the brut force approach first then the optimal. Most of the time in your videos you directly start with the optimal approach first.
Thanks a lot for your feedback, we will work on it. For better experience and precisely arranged content visit & sign up to nados.pepcoding.com
Sir why i
no we are doing i++ inside the loop
sir yeh sol gfg pr tle de rha , 10^5 pr nhi chl rha. Any idea why???
Yeah same... Did u try sliding window
just wowwww....
I am glad you liked it. I also hope that you are watching till end and trying to understand the what, how and especially why of the problem.
If you like our efforts, we request a review
g.page/Pepcoding/review?rc
You can subscribe to our channel here
czcams.com/users/Pepcodingabout?view_as=subscriber
Mast solution sir❤️❤️
Glad you liked it.
For better experience and well organised content explore nados.pepcoding.com
In c++ (-1
thanks, man I just put that extra condition, and my code got accepted
Hi,
Isn't it that your code will fail for finding smallest string for the below:
abcdefaghjklabce
abce
The answer should be abce which is present at the end however your program will return abcde.
Same query I am having
sir acquire and release is same as sliding window??
yes
can anybody explain
why are we start collecting from j+1 why not from j and starting j from zero instead of -1 don't you think there is mistake in this line
doing this we get correct indexes of i and j for substring function
you can just do j++ first and make current case susbtring as s1.susbtring(j,i+1)
Love u sir
Thankyou beta!
I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem.
If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
@@Pepcoding yes
I guess time complexity is O(n^2)
Space : O(1)
OP Sir
Glad to know that you liked the content and thank you for appreciating.
The love and respect which I get from you people keep me highly motivated and the same I am able to forward It to you people through my videos.
So, keep motivating, keep learning and keep loving Pepcoding😊
acquire
release
repeat step1 and step2
You are great sir....👍👌👌....very cool explanation 😊😊.Sir Web Dev ka vedio kab ayega ??
Very soon and Thanks alot beta Keep learning, Keep growing and keep loving Pepcoding!😊
kbhi ni
C++ Code same as the explained in the video :
string minWindow(string s, string t) {
string ans = "";
unordered_map map2;
for(auto c : t){
map2[c]++;
}
int matchcount = 0;
int desiredcount = t.length();
unordered_map map1;
int i=0,j=0;
while(true){
bool flag1 = false;
bool flag2 = false;
//acquire
while(i
I tried the same code but with i=-1 and j=-1 but somehow the flow skips the inside while loop do you have any idea on it?
string smallestWindow (string s, string t)
{
// Your code here
string ans="";
unordered_map mp1;
unordered_map mp2;
int mct=0;
int dmct=t.length();
for(auto it : t)
mp2[it]++;
int i=-1;
int j=-1;
while(true){
bool f1=false;
bool f2=false;
// cout
@@techyguy7776 in while loop put extra (i==-1) condition i.e :- while(i==-1 or i
Great explanation sir but this is giving TLE in leetcode
Sir yhe classes kab upload hongi website prr. Orr roj ki timings kya h .?
beta timings as in? ye kal sham tak site pe upload ho jaenge
@@Pepcoding ok sir thanku.