Remove Duplicate Letters | Why Monotonic Stack | Intuition | GOOGLE | Leetcode - 316
Вставка
- Опубліковано 12 вер 2024
- Similar Problem :
Leetcode-1081 - leetcode.com/p...
This is the 20th Video on our strings Playlist.
In this video we will try to solve a very good Problem - Remove Duplicate Letters (Leetcode-316).
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Problem Name : Remove Duplicate Letters
Company Tags : GOOGLE
My solutions on Github : github.com/MAZ...
Leetcode Link : leetcode.com/p...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My GitHub Repo for interview preparation : github.com/MAZ...
Subscribe to my channel : / @codestorywithmik
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook
Just saw a video of Vans Amen about it and understood nothing, just saw your video and understood everything. You really explain it very well.
It means a lot to me Raj.
Thank you for trusting my content ❤️😇🙏
Who is Vans Amen ?
@@wearevacationuncoverers Another youtube creator who posts leetcode solutions, his leetcode solution posts are pretty detailed though.
First time heard this name.
Bhaiya, The way you make question feels so easy & interesting , You deserve appreciation !
watched the video for 5 minutes and tried to solve it, I was able to solve it .
There is something magic in your explanation!
it means a lot to me.
Thank you so much 🙏❤️😇
Someone give this guy a reward ❤. Complete LEGEND
If anyone is interested in "Recursion" version (Take and Not Take) can refer to this code below :
/*
At ever character i have two choices - take or not take.
I can take it if that character is not taken before.
Once I reach out of bounds, i will see my temp string and keeping updating the result which is lexically smaller
*/
class Solution {
public:
string result = "";
int n;
int unique_characters;
void solve(int idx, string s, string temp, unordered_set st) {
if(idx >= n) {
if(result == "")
result = temp;
else if(temp.size() == unique_characters) {
result = temp > result ? result : temp;
}
return;
}
if(st.find(s[idx]) == st.end()) {
temp.push_back(s[idx]); //taking idx'th char
st.insert(s[idx]);
solve(idx+1, s, temp, st);
//Removing it for trying "Not Taking this Char"
st.erase(s[idx]); //Not taking idx'th char
temp.pop_back();
}
solve(idx+1, s, temp, st);
}
string removeDuplicateLetters(string s) {
n = s.length();
unordered_set st;
for(char &ch : s) {
st.insert(ch);
}
unique_characters = st.size();
st.clear();
solve(0, s, "", st);
return result;
}
};
Bhhaiya Subha Se colg me 3 4 ladke including me lge hue the is question ke peeche Logic to smjh gye the bas last moment me kuch test cases aakr phas gye the. But aapki video dekh kr ek dm logic smjh aa gya.
Love from ghaziabad
Thank you 😇🙏
So glad to hear ❤️❤️
hey, I don't know your real name , but I have been following you from few weeks , and you are one of the educators I can connect with, I won't say best, cause that's relative and different people connect with different individuals , but for me, you are almost perfect explainer. I would love to connect with you on twitter, if you are, Thanks.
great story telling buddy, thank you for your explanation I was able to code with that story only.
So glad to hear. Thank you for watching 😇❤️
Your content is too good sir Thanks for such content🤩
Thank you 😇🙏
as you mentioned we will only pop if we have the same character which is on the top of the stack available in our remaining string just after watching 5 minutes i coded it by myself and passes
277 / 290 test cases then realized if the chacater is already pushed in stack we dont need to take care of that and then get accepted here is my code
class Solution {
public:
string removeDuplicateLetters(string s){
int freq[26]={0};
vector visited(26,false);
stack stk;
for(auto& c:s) freq[c-'a']++;
for(auto& c:s){
while(!stk.empty() && stk.top() > c && freq[(int)(stk.top()-'a')] > 0 && !visited[c-'a'] ){
visited[(int)(stk.top()-'a')]=false;
stk.pop();
}
if(!visited[c-'a']){
stk.push(c);
visited[c-'a']=true;
}
freq[c-'a']--;
}
string res;
while(!stk.empty()) {
res.push_back(stk.top());
stk.pop();
}
reverse(res.begin(),res.end());
return res;
}
};
Awesome 😇😎
this is the recursion+backtracking solution of today's LC potd (giving TLE but this is the first approach which came to mind hope it helps others)
class Solution {
public:
string ans;
void solve(int idx, string &s, string &temp, set&st2, set&st1){
if(st1.size()==st2.size()){
if(ans.size()>temp.size()){
ans = temp;
}
if(ans.size()==temp.size())ans = min(ans, temp);
return;
}
if(idx==s.size())return;
// take only if the current char not in set
if(st2.find(s[idx])==st2.end()){
st2.insert(s[idx]);
temp+=s[idx];
// cout
This is unbelievable. My recursion code is exactly similar to yours ❣❣❣❣
I feel so proud and happy to see you coded this up. Thank you so much for sharing ❤❤❤❤
@@codestorywithMIK I am so so happy MIK for your comment 🥺❤️
I was struggling since the morning for this question, tysm for this explanation
Thank you 😇🙏
Bhaiya aapke Vedios mai ek alag hi feel vibe hoti hain ❤❤❤❤❤❤
Means a lot. Thank you 😇🙏
This channel is a goldmine that i found
May you get more n more success bhai❤️
Thank you so much ♥️♥️🙏🙏😇😇
Very greatly explained. The question felt like a cakewalk. Thanks!!
Thank you for watching 🙏😇
aise story kbhi nhin sunethe❤❤❤
Thank you 😇🙏
Phenomenal video aur Hindi me to mazaa hi aa Gaya
mast ek dum
Thank you 😇🙏
Really loved your approach on how you explain the solution.
Glad it was helpful! ❤️
Couldn't think of stack. Great explaination
Thank you 😇🙏
thanks for the intuition had thought of stack first but 2nd test case came out wrong with my approach because i tried to it like remove adjacent letters on duplicate case by sorting
Thank you 😇🙏
great question with nice explanation
Legendary explaination
Thanks for the explaining this. But please update both the arrays in parallel during processing otherwise it difficult to follow in one go. 😢😢
Your channel is growing like boooooommm..and everyone knows the reason..they are in love with the story ❤me too😅
Means a lot. Thank you so much 😇❤️🙏
Bro your explanation is perfect, thank you
Nice Explanation mik bhaiyya here is the code of this using stack in java
public String removeDuplicateLetters(String s) {
char [] arr=s.toCharArray();
int[] lastIndex=new int[26];
boolean [] taken=new boolean[26];
Arrays.fill(taken,false);
for(int i=0;i i)
{
taken[stk.peek()-'a']=false;
stk.pop();
}
stk.push(ch);
taken[idx]=true;
}
StringBuilder result=new StringBuilder();
while(!stk.isEmpty())
{
result.append(stk.pop());
}
return result.reverse().toString();
}
good explanation understood 👍
Glad it helped ❤️
story smjh aane k baad b roo diya bhai me, solution bnane me
mene like kr dia, baaki sb tere solution ki tarah, tu king hai
Sir, please bring some questions where the idea of Lexicographical order is infused!
❤❤❤ this question came in oracle online assessment this year.
Thank you so much for informing about this ❤️❤️
sir ye Sheldon Cooper Algorithm's hai --->
class Solution {
public:
bool presentstack[26]={};
int lastindex[26]={0};
//sheldon cooper used
int k ;
string removeDuplicateLetters(string s) {
stackst;
//last index fetch from presentstack
for(int i=0;s[i]!='\0';i++){
lastindex[s[i]-'a']=i;
}
for(int i=0;s[i]!='\0';i++){
char ch = s[i];
if(!presentstack[ch-'a']){
//check value that are present or not in stack
while(!st.empty() and ch < st.top() and lastindex[st.top()-'a']>i){
presentstack[st.top()-'a']=false;
st.pop();
}
st.push(ch);
presentstack[ch-'a']=true;
}
}
k =s.size();
string str ="";
while(!st.empty()){
str +=st.top();
st.pop();
}
reverse(begin(str),end(str));
return str;
}
};
Great Video 🔥
Thank you 😇
Sir is your graph playlist is complete or not?
Btw it is very very very helpful ❤❤
Only 2-3 videos left.
Will upload tomorrow soon 😇❤️🙏
Amazing explanation Sir
Thanks a lot ❤️❤️
Nice❤❤❤
How do you explain your intuition of using a stack to the interviewer?
If you notice, when I input a character in the result, there are chances I will have to remove it if I find a better alternative (lexically smaller) . So removing the character from behind is the nature of stack only. The best data structure to handle such situations is stack. Hope this will make sense in the interview ❤️❤️
Just saw the thumbnail about monotonic stack and was able to solve😂
Wow 😇🙏
thank y sir
Most welcome 😇
Sir Can you make a video of recursive solution of this question??
Hi there,
I have shared the recursive code in the comment and also in the GitHub link in the description. Give it a look, it’s simple based on take/not take concept.
Really hope that will help 😇❤️🙏
The story. uffff ❣
masterpiece
bhaiya mst smjhaya ...thankyou++ ;
Thank you 😇🙏
@codestorywithMIK
Ye recursion se try karne ka kosis kiya mei take not take
Take tab hoga jab set mei wo character nhi hoga pahle se and temp ek another string jisme wo character add hoga and jab idx== s.size() hoga and set1.size=set2.size ( set 1 s ke sare char ko store karega and set 2 take case wale char ko) higa tab sort kardenge temp ko and not take se pahle set2 se remove karenge and temp se pop back karenge!! Please MIk help with this logic
Hi Sachin,
Sounds like a valid approach. At ever character i have two choices - take or not take.
I can take it if that character is not taken before.
Once I reach out of bounds, i will see my temp string and keeping updating the result which is lexically smaller
@@codestorywithMIK MIk i have posted my code in the comment just look at it once pls
Best explanation as always
Thank you ☺️
thank you sir♥
Thank you 😇🙏
bhaiya ek leetcode ques hai Set matrix zeros please isper ek bnado code nd all please please
Guruji. Tussi great ho
Means a lot 😇🙏
Mast ekdm
❤
if it is possible can u make videos on Leetcode contest questions
I will soon start planning that once I get back to India soon 😇🙏
👍
you are taking result to return the final result, that would be some extra space right ?
We usually dont consider the space taken to store result (that we have to return).
But you can mention to the interviewer that you have taken this space for storing the result, apart from that we are not taking any extra space.
Loved the story ❤❤❤
bhaiya pair kahan hai apke 🙇♂🙇♂. You just made it easy .
🤗 means a lot. 🤝
i use MAP it little bit easy but it will take log n time extra for search 😅
Awesome 🙌
thank u
You're welcome! 😇
Thanku bhaiya ❤
Thank you for watching😇❤️
Sir Ye array wala you usme. (- 'a') wala concept kon se video mein explanin liya tha. ?
Sort by frequency daalo string question hoga usme kiya hoga
@@k.vabhavmishra th anks
Size = size * (ch -'0') sir pls explain this line..!!
ASCII value of ‘0’ is = 48
ASCII value of ‘1’ is = 49
ASCII value of ‘2’ is = 50
And so on…
Suppose ch = ‘2’,
Now when you do ch - ‘0’,
It gives 50 - 48 = 2
So if you see, from char ‘2’ , we are able to get integer 2 by doing ch - ‘0’
Now, size = size * (ch -‘0’)
Is done in order to find the size of resultant string if it’s repeated ch-‘0’ times.
@@codestorywithMIK nice sir
bawaal 🔥content
Thank you so much 🙏😇❤️
Pls start gfg potd as well
I will plan that as well when i get back to India soon ❤️❤️
Input: s = "cbacdcbc"
Output: "acdb"
Bro yahan end me c kyun nii aya
every letter appears only once.
Bro I'm getting runtime error in this code:-- (where am I going wrong ?)
class Solution {
public:
string removeDuplicateLetters(string s) {
vector last(27,0);
vector taken(27,false);
for(int i=0; is[i] && last[ch-'a']>i)
{
taken[s[i]-'a'] = false;
result.pop_back();
}
result.push_back(s[i]);
taken[s[i]-'a'] = true;
}
return result;
}
};
Can we solve it with DP too? I mean, with recursion and memoization. I immediately thought of DP. Can't this also be solved with 01 Knapsack?
I mean, DP(01 knapsack) and memoization.
I think you can.
For every character you have two options, when you reach end, keep storing the smallest lexicographically result.
Good point 👌👍🏻
@@codestorywithMIKWhen I tried it I was able to generate the smallest lexo string. I was seeing that in my console logs. But I was returning the wrong string everytime. Can I share the code, if you don't mind?
@aadil4236 Sure please share. I will have a look by evening. ❤️
@@codestorywithMIK Thank you man!
26/30
Yo