1081. Smallest Subsequence of Distinct Characters | Hindi | Java Solution

[00:00:00]Hi friends, so in this video we will see this particular program. This is a very good program friends. So first understand it with patience and then implement it. So basically we will get a string. To return is a subsequence. There are two conditions in the subsequence.

[00:00:15]First of all, all the characters should be distinct. And secondly, it should be lexicographically smallest. In simple words, if all the subsequences are arranged in dictionary order, then the first subsequence is required as an answer. Ok? Now let's discuss this a little more. Now, for example, one of its subsequences could be BCA.

[00:00:39]Now see in this, the property of distinct is being fulfilled because all three BCA are different. And all the distinct characters in this string are included in it. Now let's take another sequence.

[00:00:51]B A & C from Letts. Here we write B.A.C. So friends, we can also skip any character in the sub sequence.

[00:01:01]But we have taken care to include all the distinct characters in it. Let's have one of the CABs.

[00:01:07]In this also all three characters are coming and that too only once.

[00:01:10]And let's say one of these can also be a b c so many such subsequences are possible. Whatever fulfils both these conditions will be the answer. So everyone is fulfilling the first condition. What if we arrange this lexicographically? ABC will come first.

[00:01:29]Correct? So that's why its answer is A B C.

[00:01:33]Friends, this is the basic problem statement. Now let us see how we can approach this and how we can solve it.

[00:01:39]Now let us discuss the approach with another example. So friends, what will you do with the result that will be computed? We will pick each character from here and keep adding it. So I added C.

[00:01:54]Then B went to the next character. Now before adding B, let us see C here. So if we talk lexicographically, if we talk about dictionary order, then B comes before C. So we can remove C.

[00:02:08]But before removing C, we will ask the question whether C is coming later also? So he will say yes brother, I am coming later.

[00:02:15]C is coming here and also coming forward.

[00:02:17]So we can remove C. And we will add B here. Then we will proceed to A.

[00:02:24]So A comes before B in dictionary order.

[00:02:29]But now before removing B, we will ask whether B is coming again? So here we can see B is coming again. So we can remove B without any problem.

[00:02:40]And added A. Proceed as usual C. Now C comes only after A. So there is no problem. Let's add this.

[00:02:48]Then proceeded D. So friends, D also comes only after C. So we can add D also. Then came C. Now we have already added C, so we will not add this.

[00:03:00]So from here we draw a little conclusion that we will have to keep something called visited in which we will know that friends, the person who has already visited should not be added. Right? So we will skip C here. Now we will come here to B. Now before adding B, we will see that B comes after B. So we would like to remove it. But we'll ask is d coming later? So d is not coming after this. So we will not be able to remove d. So to check all this we will have to keep a frequency.

[00:03:38]While implementing the code, we will understand better whether brother d is ahead or not. Does he have an appearance or not? To find this out, we can maintain a frequency. So what do we do here? We will add B. And then came C. Now C has arrived. Already visited. Isn't it? If it is there then we will not add it. So ultimately our answer will be this answer. That is why we can see that the answer is A C D B.

[00:04:11]I hope we have got some clarity on how to approach this.

[00:04:15]Now let us implement and we will get more clarity in the implementation.

[00:04:20]So first of all let's create an array of frequencies which will keep count of how many times a character has appeared. Now friends, here I am writing 126. Actually it is given that only small letters will come from small a to small z. And the S key code of small z is 97 and that of z is 122.

[00:04:42]So, in between this, we bring SK code.

[00:04:45]So I've taken 126. Pretty safe, right? So you can use this. Otherwise, the more specific recommendation is that you should take an array of size 26 and its indexing should be from zero to 25. But there we will have to do some management, A which is 97 will have to be converted into zero.

[00:05:06]So I avoid that and take 126. It's not a big number and won't add much load to the program. But this is your choice.

[00:05:15]How do you want to do it? I took 126 like this.

[00:05:18]Similarly, I take a boolean array which will tell whether it is visited or not. Has that element already appeared in our results? And I will also buy size 126.

[00:05:31]What now? First I fill the array with frequencies.

[00:05:36]Meaning, I bring out each character one by one. And which character has appeared how many times, like how many times has A appeared, it has appeared twice, it has appeared thrice, I maintain the number of times it has appeared. I write carry and s to the carry array. So basically, one character at a time will come out and appear in ch. And then we go to the CH index and increase its count. So here we write frequency CH plus plus.

[00:06:02]After this loop, we have a count of all the characters, showing how many times each character has appeared.

[00:06:08]Now basically we had to insert the character and pop it and so on. So for that I take array list to maintain that thing.

[00:06:16]As we discussed, if a big character comes, C comes and we have to insert A.

[00:06:23]So we were removing like C.

[00:06:25]So array list will help us a little in that.

[00:06:30]To basically store the characters, we take an array list. Let's name it ST because we will use it as a stack and here we run the loop carry CS to carry array and first of all we check whether it is visited or not. If he is visited it means he has to be skipped. As we had discussed. Here we write visited of ch double = true if it is visited then first thing we reduce its frequency. That's why we are minus the frequency.

[00:07:06]And what are we doing from here? Continue that brother, go and fetch the next character.

[00:07:10]This character has no work.

[00:07:13]Because this is already in our result.

[00:07:16]Now first of all we take the size of the stack i.e. how many characters are there in it. So int size = st dot size. And all the operations that will take place will matter only on the size.

[00:07:28]So here we write that size > 0. Now size greater than 0 means that in the result we were talking about, some characters are already there in ST. So let's actually fetch the topmost character so that we can compare whether it is bigger or smaller.

[00:07:45]Here we write carry tum = st dot gate size -1. Ok? So when indexing happens, we will have to make size -1 to get the last character. And first of all let us check whether the character is bigger than our CH or not. If the right end is big, now we have to check whether it is coming later or not.

[00:08:12]Before removing it, we were checking whether it would come later or not. If it is coming later and is also big then we will remove it because it can be added later.

[00:08:20]So here let's check frequency time > 0. So friends, you have to understand this. This condition is indicating that this character is coming later. Ok? That's when we were removing it.

[00:08:33]Remember? So here we will do ST remove and size - one. That brother, you should remove this character from the team.

[00:08:43]Ok? Now mark the visited ones as false.

[00:08:52]Mark the falls as visited.

[00:08:55]Because now it is not in the result, it will have to be added to the result later. Ok? So here we marked it false.

[00:09:03]If it is not fulfilling the condition.

[00:09:05]Meaning either the temp is small or it is not coming in the time future. Then what can we do? Then we basically do n't have to take any special steps. We have to enter whatever character comes.

[00:09:18]So we will do that work after the while loop. So what do we do to the while loop now? Let's break it and we come out of the vile loop.

[00:09:27]Friends, if one character gets removed, then we will go to the other character and try to remove it. So what will we do here? We will also reduce the size by one so that if one character is removed, C may come first.

[00:09:42]Removed it. After that, it may happen that B also has to be removed. Because in B we have to insert the character A. Ok? So that's why we reduced the size here by one.

[00:09:50]What do we do now? Whatever character was there, we added it.

[00:09:56]Add CH and mark visited as true because this has already come in our answer.

[00:10:04]So here we write visited CH = true.

[00:10:09]And its frequency is also reduced.

[00:10:13]Right? Now friends after this loop we have the result in ST. Now basically we have to convert it into a string and return it because what we have to return is a string. Ok? So here we create a string builder that works fast. Whenever we have to do manipulation then String builder is much better. And here we write for carry CH ST, we will keep removing the carry from ST and will keep appending it in the string builder and will just return it here. We convert SP to string and that's it. I think we have it sorted. Let's try running it.

[00:11:00]Excellent. Sample test cases are being accepted, friends. Let's submit.

[00:11:05]Excellent. Our session is being accepted.

[00:11:08]friends. I would request you to like the video. And thank you so much for watching this video. See you in the next video. Yes.