Minimum Window Substring (Leetcode Hard) | Hashmap Interview Questions
Вставка
- Опубліковано 19 вер 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.
Hard question and simple explaination, maza aa gya sir💯
thank you
Superb explanation!
Amazing explanation - this is an understatement!
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
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 )
you are the reason why i am getting interested in programming.
thank you
You explained this hard problem in such an easy way. Thankyou :)
Great explanation. I was scratching my head whole day reading about this solution online.
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
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
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
Sir, Your explanation is one of the greatest thank you so much.
sir you gave outstanding explanation with a simple code. love the way of your teaching
:)
Wow Sir !!! Mazaa hi aa gya kahin nahi mili t iski itni easy explanations .
Sir ji tussi Great ho .
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
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)
"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!
Brilliant explanation!! Thank you sir
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
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
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 🙏
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.
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!!!
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
Thanks a lot sir to make me understand this hard problem.
You make this problem is so easy for us. Thank you so much sir
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
your explanation is very easy for this hard question ,thanks sir
Nice explanation sir.....thanks for making the video
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
Aap to bade heavy driver nikle
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
ua-cam.com/users/Pepcodingabout?view_as=subscriber
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, 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.
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 )
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
superb explaination
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
Perfect explanation. Couldn't resist to comment
Really good explanation
I guess time complexity is O(n^2)
Space : O(1)
Nice explanation!!
great explanation sir, thank you very much.
This man is clearly underrated
Hope you love the explanation, for better experience and well organised content visit - nados.io
best explaination❤
thanks bro, very good explanation. keep up the good work.
Your explanation is soo simple.
Thank you so much. Keep learning, Keep growing and keep loving Pepcoding!😊
Awesome Explaination indeed !!!
the way you explain is superb..thanks
You are most welcome
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 )
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
easy to understand thank you sir
Can't be better than this...No way...
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 )
This was lit🔥
Thanku sir❤️❤️
Thank you so much sir!
acquire
release
repeat step1 and step2
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 )
why we are doing minus i.e while i
otherwise it will throw string index out of bound exception...
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
Sir, what is the space and time complexity of the solution?
Done!
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
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?
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
ua-cam.com/users/Pepcodingabout?view_as=subscriber
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) ?
Lovely explanation brother🙌🙌🔥🔥
jara submit kriyo ye code leetcode pe
Nice explanation. May I know what is the tool you used for explaining the algorithm. I really liked the Tool.
That is Open Board.
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]
In c++ (-1
thanks, man I just put that extra condition, and my code got accepted
Best explanation 🙏🙏🔥🔥
Glad you liked it
you are amazing :)
Mast solution sir❤️❤️
Glad you liked it.
For better experience and well organised content explore nados.pepcoding.com
Time Complexity?
EXPLANATION IS SUPERB BUT the code is taking too much time sir😢
Thankyou very much sir🙏
Most welcome
java code - class Solution {
public String minWindow(String s, String t) {
HashMap map2 = new HashMap();
for(int i = 0;i
the implementation is hard the question isn't :(. so many things to take care of .
sir yeh sol gfg pr tle de rha , 10^5 pr nhi chl rha. Any idea why???
Yeah same... Did u try sliding window
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
awesome work..
Thank you sir
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
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.
Amazing explanation
Glad you think so!
If you like my efforts, I request a review
g.page/Pepcoding/review?rc
Sir why i
no we are doing i++ inside the loop
Sir, This will work with linear time complexity right ?
Great explanation sir but this is giving TLE in leetcode
Im getting memory limit exceeded error, anyone can help?
❤❤
My c++ code :
----------------------
class Solution {
public:
string minWindow(string s, string t)
{
// Sliding window concept
unordered_mapmp2; // map for second string 't'
unordered_mapmp1; // map for first string 's'
string ans = "";
int n = s.length() , k = t.length() , match_count = 0 , desired_mct = t.length();
int left = -1, right = -1;
for(int i = 0;i < k;i++)
{
char ch = t[i];
mp2[ch]++;
}
while(true)
{
bool f1 = false;
bool f2 = false;
// acquire
while(right < n-1 && match_count < desired_mct)
{
f1 = true;
right++;
char ch = s[right];
mp1[ch]++;
if(mp1[ch]
what is the time complexity?
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