Minimum Window Substring (Leetcode Hard) | Hashmap Interview Questions
ฝัง
- เผยแพร่เมื่อ 16 ก.ย. 2024
- 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....
For a better experience and more exercises, VISIT: www.pepcoding....
Have a look at our result: www.pepcoding....
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.
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.
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
Hard question and simple explaination, maza aa gya sir💯
thank you
Superb explanation!
Amazing explanation - this is an understatement!
You explained this hard problem in such an easy way. Thankyou :)
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 )
sir you gave outstanding explanation with a simple code. love the way of your teaching
:)
Great explanation. I was scratching my head whole day reading about this solution online.
Sir, Your explanation is one of the greatest thank you so much.
Sir, you are the best🖤. Just understood the whole concept of the problem and approach within 6min. Great explanation
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
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
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
"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 have seen a lot of video before landing here but you have given a very clear explanation .. great work man :)
Glad it was helpful!
This question seems simple but isn't. GG on explaining it!
haina!!
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
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.
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)
Wow Sir !!! Mazaa hi aa gya kahin nahi mili t iski itni easy explanations .
Sir ji tussi Great ho .
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
Brilliant explanation!! Thank you sir
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
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
you are a great teacher sir
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 🙏
Thanks a lot sir to make me understand this hard problem.
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
Nice explanation sir.....thanks for making the video
You make this problem is so easy for us. Thank you so much sir
your explanation is very easy for this hard question ,thanks 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!!!
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)
superb explaination
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
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
th-cam.com/users/Pepcodingabout?view_as=subscriber
I guess time complexity is O(n^2)
Space : O(1)
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
best explaination❤
Nice explanation!!
Aap to bade heavy driver nikle
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
Really good explanation
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, 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.
We can also use array instead of hashmap..
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
Perfect explanation. Couldn't resist to comment
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 )
great explanation sir, thank you very much.
thanks bro, very good explanation. keep up the good work.
Sir, what is the space and time complexity of the solution?
the way you explain is superb..thanks
You are most welcome
This man is clearly underrated
Hope you love the explanation, for better experience and well organised content visit - nados.io
Your explanation is soo simple.
Thank you so much. Keep learning, Keep growing and keep loving Pepcoding!😊
Awesome Explaination indeed !!!
easy to understand thank you sir
EXPLANATION IS SUPERB BUT the code is taking too much time sir😢
acquire
release
repeat step1 and step2
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?
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 )
In c++ (-1
thanks, man I just put that extra condition, and my code got accepted
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.
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 )
Can't be better than this...No way...
Done!
the implementation is hard the question isn't :(. so many things to take care of .
Time Complexity?
This was lit🔥
Thanku sir❤️❤️
Thank you so much sir!
why we are doing minus i.e while i
otherwise it will throw string index out of bound exception...
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) ?
Great explanation sir but this is giving TLE in leetcode
Lovely explanation brother🙌🙌🔥🔥
jara submit kriyo ye code leetcode pe
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
th-cam.com/users/Pepcodingabout?view_as=subscriber
Nice explanation. May I know what is the tool you used for explaining the algorithm. I really liked the Tool.
That is Open Board.
sir yeh sol gfg pr tle de rha , 10^5 pr nhi chl rha. Any idea why???
Yeah same... Did u try sliding window
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
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
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.
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
Im getting memory limit exceeded error, anyone can help?
Sir why i
no we are doing i++ inside the loop
Best explanation 🙏🙏🔥🔥
Glad you liked it
Python Code:
def minWindow( s, t):
m = len(s)
if m == 0:
return ''"
# Compute frequency of chars in t
freqT = {}
for c in t:
freqT[c] = freqT.get(c, 0) + 1
i = 0
j = 0
n = len(t)
freqS = {}
output = ''
matchCount = 0
while i < m:
# Acquire chars and update of chars in s
while i < m and matchCount != n:
c = s[i]
freqS[c] = freqS.get(c, 0) + 1
if freqS[c]
Sir, This will work with linear time complexity right ?
Thankyou very much sir🙏
Most welcome
sir what is the time complexity for the above question?
Mast solution sir❤️❤️
Glad you liked it.
For better experience and well organised content explore nados.pepcoding.com
you are amazing :)
This ans is giving me a TLE . Its written in c++. please do read it
string minWindow(string s, string t) {
string ans="";
unordered_map map2;
for(auto &a: t)
map2[a]++;
int mct=0;
int dmct=t.length();
unordered_map map1;
int i=-1;
int j=-1;
while(true)
{
bool f1=false;
bool f2=false;
while(i
Beta koi edge case miss ho rh hoga, ek bari aache se dubara analyse kr k dekho. I'll even check it once again.
sure sir i am checking it
@@bighneshkumarpati8640 break conditon will be flag1==false and f2==false
still its coming wrong
class Solution {
public:
string minWindow(string s, string t) {
string ans="";
unordered_map map2;
for(auto &a: t)
map2[a]++;
int mct=0;
int dmct=t.length();
unordered_map map1;
int i=0,j=0;
while(true)
{
bool f1=false;
bool f2=false;
while(i
what is the time complexity?
awesome work..
Thank you sir
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)
Amazing explanation
Glad you think so!
If you like my efforts, I request a review
g.page/Pepcoding/review?rc
java code - class Solution {
public String minWindow(String s, String t) {
HashMap map2 = new HashMap();
for(int i = 0;i
❤❤