Minimum Window Substring (Leetcode Hard) | Hashmap Interview Questions

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

[@alfiyazahra4680]

sir, your explanation is damn perfect. every time search for a coding solution, I wish I found pepcoding there.

[@Pepcoding]

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😊

[@alfiyazahra4680]

@@Pepcoding yes sir U r just awesome

[@pranjalgusain21]

Very Engaging and DETAILED explanation! I am naturally Extra Focused during his videos.

[@TheProblemSolvers38]

I think no one can explain these tricky solutions better then you sir ......... : )

[@Pepcoding]

Thanks a lot, for better experience and well organised content sign up on nados.io and start learning.

[@shoryasharma9758]

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

[@Akshitgupta1]

Hard question and simple explaination, maza aa gya sir💯

[@Pepcoding]

thank you

[@SugamMaheshwari]

Superb explanation!

[@9891830620]

Amazing explanation - this is an understatement!

[@alonewolf7682]

you are the reason why i am getting interested in programming. thank you

[@bharathpn4906]

Great explanation. I was scratching my head whole day reading about this solution online.

[@shivanivishwakarma2350]

You explained this hard problem in such an easy way. Thankyou :)

[@shambhurajeshirke2970]

sir you gave outstanding explanation with a simple code. love the way of your teaching :)

[@saichaithrik7134]

Sir, Your explanation is one of the greatest thank you so much.

[@ajaywadhwa3398]

Wow Sir !!! Mazaa hi aa gya kahin nahi mili t iski itni easy explanations . Sir ji tussi Great ho .

[@chandankumartandi3842]

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)....

[@Pepcoding]

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 )

[@soumavanag5025]

The concept is very tricky and very useful for other problems as well. It gives a new perspective to solve a problem. Thank you :)

[@ommapari]

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

[@ommapari]

@@Kashish_Batra Lag gai

[@mr.k6831]

Sir, you are the best🖤. Just understood the whole concept of the problem and approach within 6min. Great explanation

[@minkalchaudhary1977]

I understood in half way you make hard question so easy.Thank you sir you are doing great job👍.

[@Pepcoding]

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

[@anuragagnihotri5238]

"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 :)

[@tejanikhil3603]

Brilliant explanation!! Thank you sir

[@brijpatel237]

watched till half and boom got the green tick! , thanks :-D

[@Pepcoding]

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)

[@ankushgupta630]

This question seems simple but isn't. GG on explaining it!

[@Pepcoding]

haina!!

[@subhasishhalder4817]

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

[@shishirpandey7762]

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.

[@aryannagraj4681]

you are a great teacher sir

[@ssr5052]

I have seen a lot of video before landing here but you have given a very clear explanation .. great work man :)

[@Pepcoding]

Glad it was helpful!

[@warmachine9097]

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

[@shamsfiroz01]

Thanks a lot sir to make me understand this hard problem.

[@rohita6532]

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; } };

[@IT__PRANJAL_BAJPAI]

You saved a lot of my time, tnx

[@CodeSuccessChronicle]

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 🙏

[@paragroy5359]

Nice explanation sir.....thanks for making the video

[@marvel438]

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; }

[@pulkitjain5159]

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:)

[@pratik.784]

tle aajayega

[@enigma2886]

Aap to bade heavy driver nikle

[@snehajain5562]

your explanation is very easy for this hard question ,thanks sir

[@AyushRaj-pm1dz]

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

[@techyguy7776]

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?

[@techyguy7776]

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

[@ROHITKUMAR-xp2xe]

@@techyguy7776 in while loop put extra (i==-1) condition i.e :- while(i==-1 or i

[@srilathareddy9450]

superb explaination

[@dineshsrivastava4508]

You make this problem is so easy for us. Thank you so much sir

[@anas7175]

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

[@Pepcoding]

Glad it helped! For better experience and precisely arranged content visit on nados.io

[@VishalKumar-tn8ls]

Perfect explanation. Couldn't resist to comment

[@virajpatil5310]

Nice explanation!!

[@kashifanwar4264]

Kya explain Kiya h sir.. outstanding😊

[@Pepcoding]

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 )

[@garimagarg9065]

Sir, honestly aap humari hopes ko alive rkhte ho.

[@Pepcoding]

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.

[@GunjanKumar-ls9ix]

Hard Problems seems easy after your video, good job sir.

[@Pepcoding]

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 kzbin.infoabout?view_as=subscriber

[@satwikjain6177]

Really good explanation

[@priyanshukumawat4142]

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 !!!

[@Pepcoding]

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.

[@priyanshukumawat4142]

@@Pepcoding SURELY!!!

[@AmanKumar-wd2mq]

best explaination❤

[@BCS_VickyGupta]

We can also use array instead of hashmap..

[@friendsav1244]

thanks bro, very good explanation. keep up the good work.

[@rutwikmore7462]

Awesome Explaination indeed !!!

[@senvikas1946]

great explanation sir, thank you very much.

[@shreyamoghe6893]

Awesome explanation! Seriously great, you keep us glued to the video till the end. I had one ques what would be its time complexity?

[@girikgarg1268]

Yes same question, what would be the time complexity?

[@AbhijeetSachdev]

O(n)

[@vivekkejriwal3321]

This man is clearly underrated

[@Pepcoding]

Hope you love the explanation, for better experience and well organised content visit - nados.io

[@abhishekjha2182]

Your explanation is soo simple.

[@Pepcoding]

Thank you so much. Keep learning, Keep growing and keep loving Pepcoding!😊

[@letsdoeverythinginoneweek9398]

nice explanation after watching so many videos this video is so much helpfullllll........

[@Pepcoding]

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 )

[@ajeetworking]

the way you explain is superb..thanks

[@Pepcoding]

You are most welcome

[@anujchetwani7310]

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

[@hunainnasir520]

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.

[@VishalKumar-tn8ls]

Same query I am having

[@rawat_ji5183]

easy to understand thank you sir

[@shreyjain2357]

Sir, what is the space and time complexity of the solution?

[@suhitgupta9429]

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.

[@Pepcoding]

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

[@mainakmondal5228]

Can't be better than this...No way...

[@hari7027]

I guess time complexity is O(n^2) Space : O(1)

[@youngshahrukhkhan8179]

Very Nice Explanation.......Keep making videos

[@Pepcoding]

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 )

[@sadlyf2056]

In c++ (-1

[@maheriyajatinbharatbhai3538]

thanks, man I just put that extra condition, and my code got accepted

[@pankajkohli9263]

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 :)

[@Pepcoding]

Yes, sure

[@pranavsharma7479]

string matching algos then

[@janhavipatil4971]

Thank you so much sir!

[@rohandevaki4349]

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?

[@satyamgupta1416]

why we are doing minus i.e while i

[@indranilchakraborty5949]

otherwise it will throw string index out of bound exception...

[@pirangitharun8736]

Thank you so much. You explained it very clearly. and subscribed too :)

[@Pepcoding]

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 )

[@rohit8021]

This was lit🔥

[@rachelross9275]

Time Complexity?

[@cavi8779]

Loved ur explanation bhai

[@Pepcoding]

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 kzbin.infoabout?view_as=subscriber

[@songs-pu9bq]

Lovely explanation brother🙌🙌🔥🔥

[@yogeshyts]

jara submit kriyo ye code leetcode pe

[@NaveenKumar-os8dv]

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.

[@peerless3538]

EXPLANATION IS SUPERB BUT the code is taking too much time sir😢

[@noobhike5609]

Thanku sir❤️❤️

[@mishra1576]

Best explanation 🙏🙏🔥🔥

[@Pepcoding]

Glad you liked it

[@sarangr8624]

Best explanation ever

[@Pepcoding]

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

[@sravannayini4329]

Nice explanation. May I know what is the tool you used for explaining the algorithm. I really liked the Tool.

[@tusharnain6652]

That is Open Board.

[@namansrivastava2528]

sir yeh sol gfg pr tle de rha , 10^5 pr nhi chl rha. Any idea why???

[@sathishkumar-dc9ce]

Yeah same... Did u try sliding window

[@loserfruit9663]

Sir,You are best

[@Pepcoding]

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.

[@virusnetic]

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) ?

[@saikatdeyashi]

Sir, This will work with linear time complexity right ?

[@Ravi-ks7ev]

acquire release repeat step1 and step2

[@SumitSingh-ui4do]

Mast solution sir❤️❤️

[@Pepcoding]

Glad you liked it. For better experience and well organised content explore nados.pepcoding.com

[@theglamourhut]

Thankyou very much sir🙏

[@Pepcoding]

Most welcome

[@souravkumarshaw7090]

sir what is the time complexity for the above question?

[@511-neelbutani9]

Sir why i

[@aditikajale8514]

no we are doing i++ inside the loop

[@246amishakumari7]

you are amazing :)

[@dewashishwankhede2478]

Amazing explanation

[@Pepcoding]

Glad you think so!

[@Pepcoding]

If you like my efforts, I request a review g.page/Pepcoding/review?rc

[@girikgarg8]

Done!

[@lokeshnegi5051]

awesome work..

[@Pepcoding]

Thank you sir

[@indranilchakraborty5949]

You are great sir....👍👌👌....very cool explanation 😊😊.Sir Web Dev ka vedio kab ayega ??

[@Pepcoding]

Very soon and Thanks alot beta Keep learning, Keep growing and keep loving Pepcoding!😊

[@yogeshyts]

kbhi ni

[@KB-zg8ho]

Sir in this question what is an alternative version of map.getordefault in c++ ?

[@Pepcoding]

ek fn likhna hoga agar count zero hai to saamne frequency 1 daal dein. nahi to badha dein

[@rosansenapati-pl5hr]

Great explanation sir but this is giving TLE in leetcode

[@kancharlasrimannarayana7068]

what is the time complexity?

[@faizan346]

the implementation is hard the question isn't :(. so many things to take care of .

[@himanshu_047]

Im getting memory limit exceeded error, anyone can help?

[@manavkumarjaiswal2734]

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

[@mickyman753]

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)

[@aviralsrivastava7197]

sir acquire and release is same as sliding window??

[@aditikajale8514]

yes

[@rupeshsharma9235]

Sir yhe classes kab upload hongi website prr. Orr roj ki timings kya h .?

[@Pepcoding]

beta timings as in? ye kal sham tak site pe upload ho jaenge

[@rupeshsharma9235]

@@Pepcoding ok sir thanku.

[@ankoor]

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]

[@Elon-musk-007]

Sir background noise distract karti hai ?? Video's shaant jagah par banaye if possible

[@Pepcoding]

Ji dhyaan rakhunga