LeetCode 1081 | Smallest Subsequence of Distinct Characters | Monotonic Stack Trick | Python

[00:00:00]Hey everyone, how are you? So today we are going to solve the lead code problem of the day and the problem is smallest subsequence of distinct characters and the problem is of medium level but no worries we are going to make it look easy. The problem number is 1081 and the problem says that you are given a string s as an input which contains alphabet.

[00:00:22]It will basically contain lowerase alphabet like a b up to z. And what we need to find out is what we need is a lexographically smallest subsequence which contains all the characters of your given string s. For example, if the given input is this one, this is your given input string. Then the output is going to be a c d b. Basically a c db is a subsequence in the given string s a c db which contains all the characters which is in your string s. Your string s contains a b c and d. These are the four characters and the smallest lexographically smallest subsequence which contains all these four characters is a c d and b. So this is going to be your output. As you can see the example as well that the output for this given input is a c db. Now the thing is how are we going to solve it? So let's start from the basic and let's see how are we going to solve it without jumping to the actual solution. So this is your given input string S right now try to think what you actually need. You need to find out what are the unique characters in your string. Right? First of all you need to find out it then only you can just you know try to create a subsequence from your given string which contains all those unique characters. Right? So given the string I would find out the unique characters. So I have a b c d. These are the unique characters.

[00:01:51]My target is to find out a lexographically smallest subsequence. So I would try to find out a subsequence from the given string s which starts with the smallest character. Right? My target would be to find out a subsequence which starts with a then we get a b then we get a c and then we get a d. Right? So this will be my target.

[00:02:12]Now we need to find out a subsequence which is closest to our target which is going to be our final answer. So I would like to start with A. So this is my first A which I got right. So let's say that we include this first A in our subsequence. So we got a subsequence starting with A. Then we see a B here.

[00:02:31]Right? So we start with A then we see a B then we see a C. So we got A B C.

[00:02:36]Right? We got A B and C. But we have not got a D because a subsequence in a subsequence you can you cannot go back to find a D. Right? So you will have to just keep jumping forward. So we got a A we got a B we got a C but we do not have a D. So if we create a subsequence which is A B C then we cannot get a D. Right?

[00:02:55]So you cannot just go in straight way and get the answer. So let's try to get into some logical part now that how can you apply some logic and get the answer.

[00:03:04]So let's say we start with A. Right? Now we get a C here. We can include this. We get a D here. We include this. We get a C here. We already have a C. So we don't need to take this C. Then we get a B here. And we got our answer which is A C D B. Right? So you need to understand that your answer will always have a length which will be equal to the number of unique characters in your string. So if I have four unique characters, my answer will have a size of four because I don't need to include any character which is already there in my subsequence. For example, if I say A C D CB, if this is my subsequence then I could just simply remove this and still my subsequence A C DB will be correct, right? Correct for the particular solution. So based on these kind of knowledge, let's start solving it by going character by character and let's see what we can do with each character.

[00:03:54]So first we see the character C and let's say we include this in our answer right although we know that the answer for this particular is A C D B this is our subsequence or a sequence which has all the characters and it is lexographically smallest as well right but still the moment I see a C I would say let's say this is my answer this is a part of my answer and I have started creating my answer B all right let's do the same thing right we get a B and let's add it in our answer so we got a subsequence as of now of two characters which C and B. But the problem is I know that I have a character just before me which is greater than me. Right? The character before B is three and we know that C is greater than B. So this is not lexographically smallest as of now. But what if there is no any number of C available in future? We just have a D and B. Then in this case we we will have to start with a C right because we we are not going to get a C later on. So that's our logic. The moment I see a B and I see a character previous to B which is greater than B. So my question will be will I get the same character in future or not. If I get this character in future so I could actually remove this from my answer. I don't need it because I can get it in future and this will be lexographically smaller. Right?

[00:05:09]If I just remove this particular C and I know that later on I am going to get a C. So for sure I will have a C after the B. Right? This is lexographically smaller at least compared to CB, we know that BC is lexographically smallest, right? This is the smallest. So this is going to be my logic. How do I know that if I get a B and my previous character is actually a C. So how do you know that do I have a C in future? You will just have to run a loop here, right? But better thing to do is initially have a count of all the characters. If I have a count, let's say the count, initial count is going to be for C it is 1 2 and 3 and four. For B it is two. For A it is 1 and for D also I think it is one. So these are the count of my character. The moment I have seen a C the first C I would just reduce the count. For every character I have to see the future that do I have a character in future or not.

[00:06:03]Right? So for example for B I want to know that do I have a C in future or not. So the moment I will see this I will remove its count or I would decrease its count so that the remaining count is just for the future. So I have seen a C here right? So the moment I have seen a C here I would say now the count is not four the count is actually three. All right. Similarly for B the moment I see a B here I would say the count is not two the count is actually one. So let me actually write this in a more readable way. The count is one the count is three. Now the question is I got a B previously I have a C. Do I have a C in future? Yes the count is three.

[00:06:40]So I have three C. later on I would just remove this from my answer and my answer would start with a B. Now here what you are applying is a kind of stacked. The thing is I want to store my data in something like a stack because I want to go back the moment I remove a C maybe I had a D here. I had a C here or not C but let's say I have a E here right. So I would just keep removing those characters which I can get in the future. So I want to look just one step back. So having the data in a kind of stack is going to be useful for a C. If I want to add a B at the top and then before adding I would just want to verify that the previous character is it lexographically smaller or not. If it is smaller then it is fine but if it is bigger do I get the same character in future? If yes I would remove this. So I need to store it in some kind of stack and now this is a special kind of stack.

[00:07:29]This is called a monotonic stack because a monotonic stack either keeps the element in increasing order or decreasing order. Now this increasing or decreasing is decided on some kind of fact. So here we are deciding the ordering based on the availability of the element in future and based on the lexographically smaller element. So right now my answer starts with a b. Now I do the same thing with the next element which is a. So I include this a but before I include this I want to ensure that this a is not already there in my data or in my answer or in my stack. So I will have to maintain a kind of set as well where I will store all the elements in my stack so that I can just take a lookup and understand that do I need to process this element or not. If the element is already in my answer, I don't need to process it. But A is not in my answer. So I will process it and I will do the same thing for A. I will see the previous element it is B.

[00:08:22]Is B in future or not? Why I would check? Because B is more than A lexographically. So in future we do have a B, right? We have a B here and I can see it from the count itself. So I would say and before doing this the moment I see a A I would decrease its count right. So that now the count of A will be zero. The count of B is one. So I know that we have a B in future. So I can simply remove this B from my answer and my answer starts with a A. So now you know now you can see how the answer is building up. Similarly the moment I see a C here I would add it in my answer because the previous character is not more than C. Right? So right now the answer is lexographically smaller.

[00:08:59]Similarly I see a D here and if you see a D and you go to the previous element and you see that the previous element is again not lexographically bigger.

[00:09:07]Actually D is bigger right? So right now we are creating the sequence in lexographically correct form. Next I see a C but I already have a C so I ignore it. Next I have a B and before I do this since we have processed D C and now we are processing B so we need to decrease its count as well. So the count of B would be zero. The count of C would be one because we had to include this as well. I didn't decrease the count and the count of D would be zero. So now the count will be 0 0 1 0 and right now we are processing B. So the moment I process a B, I see that the previous element is actually bigger than B. So ideally we would want that this B should be before this D, right? But if I see in future I do not have a D, right? And in and in our answer we definitely need all the characters right. So I cannot remove this D because I do not have a D in future. So I would have to include this B in my answer. And the moment I include this D in my answer and process the next element which I already have, we are out of the loop and the sequence which we have got is A C D and that's our final answer. So this is the logic which we need to incorporate to solve this problem. And if I just show you the solution for this. The solution is also very simple to understand. Initially we are storing the frequency of all the characters because we need the count and we are storing a scene set which will have the elements which are going to be in our stack and this is our stack. Now we go through all the elements and the moment we see a character we decrease its frequency by one and we check that if this character is not already seen then we do a logic. The logic is while we have something in the stack and the previous element in the stack is more than the current character. It means now the lexographical order is not maintained but we have to ensure that the element which is previous we get this in future. So if the frequency of this previous element is more than zero still in that case we know that we are going to get the element in future. So I can just pop out the element. So I would say st.pop I would get that element and remove it from my set as well. And after this process is completed for the current character, I would just add it in my stack and add it in my set as well. So after this loop is over, after we have incorporated our logic, we can just join our stack elements and return it as a string and that will be our final solution. If you could submit this solution, you would get a accepted response from lead code. Runtime wise, it is really good. Memory wise, I think we could improve, but I think this is a very good solution for this particular problem. And that's it for this problem, guys. If you found this particular explanation helpful then make sure that you hit that like button and if you have not subscribed to my channel as of now then please do so because I would be uploading the daily solutions of the lead code problem of the day. So it would be helpful for you. For now I think we are good for this video. Thank you for watching. I would see you guys in the next video.