1081. Smallest Subsequence of Distinct Characters | Leetcode Daily - Python

[00:00:00]Welcome back to another daily code breakdown, let's get right into today's challenge. Today we are looking at problem 1081, smallest subsequence of distinct characters. Before we start, if anything confuses you during this video, please drop a comment below. I try my best to respond to everyone and help clear things up. Here is the problem page. It's a bit dense, so let's break down exactly what it's asking us to do step by step. Our main goal is to take a string of letters and filter it down so that every unique letter only appears exactly once in our final answer. Now, we can't just jumble the letters up however we want. Our answer must be a subsequence, meaning the letters have to stay in the same relative order they appeared in the original string. And finally, the trickiest part. Out of all the valid ways we could pick our letters, we need to pick the one that is the smallest lexographically.

[00:00:49]Basically, we want it to be as close to alphabetical order as possible like it would appear in a dictionary. Let's make this concrete with an example. Suppose our starting string is B, C, A, B, C. If we look at this string, we can see there are only three unique letters hiding in there. A, B, and C. We need to pick one of each. One option is to just take the very first B we see, then the first C, and then the only A. That gives us the string B C A. But what if we wait? If we grab the A first and then take the B and C that come after it, we get A B C.

[00:01:25]Comparing our options, A B C is much earlier in the alphabet than BCA. So ABC is our winning answer for this example.

[00:01:33]Just a quick heads up, I'll be explaining the logic using Python, but I'll show the full code for Java, C++, and JavaScript at the end of the video.

[00:01:41]The logic is identical across all of them. To solve this efficiently, we'll use an approach combining a greedy strategy with a data structure called a monotonic stack. This just means we'll build our perfect string one letter at a time, keeping it as alphabetical as possible. The greedy part is simple. As we read through our letters, if the letter we are looking at right now is alphabetically smaller than the letter we just recently put in our answer, we want to swap them. But there's a huge catch. We are required to have exactly one of every unique letter. We can only throw away a letter we previously picked if we are absolutely certain there is another copy of that same letter waiting for us later in the string. Okay, let's look at the setup code. We create two lists of 26 zeros, one for each letter of the alphabet. First, we loop through our string and count up exactly how many times each letter appears. This is how we'll know if a letter shows up again later. We also create an empty list called our stack. We will use this to slowly build our final answer, adding and removing letters from the end of it as we go. Now for the main event, we loop through every single character in our string one by one. We also figure out the alphabet index for our character. So A is zero, B is one, and so on. Before we do anything, we check our visited list. If we already have the current letter sitting safely inside our stack, we completely ignore it and move on. We only want one of each, after all.

[00:03:03]If it's a new letter, we enter a loop.

[00:03:05]We check the top item on our stack. Is it alphabetically larger than the letter we are holding right now? If it is, it's making our sequence worse, so we might want to get rid of it. We look at our counts list to see if there are any more copies of that top letter coming up later in the string. If there are, it's safe to throw it away. We mark it as no longer visited and pop it off the stack.

[00:03:24]But if our count says zero, it means that letter is the very last one of its kind. Even if it's ruining our alphabetical order, we are forced to keep it. So, we break out of the checking loop. Once we've popped off all the larger letters we safely could, we mark our current letter as visited and stick it onto the top of our stack.

[00:03:42]Crucially, whether we added the letter to the stack or skipped it, we must decrease its count in our remaining counts list because we've now processed this position in the string. Finally, once the loop finishes, our stack contains the perfect sequence. We just join the characters together into a solid string and return it. Here is how that all looks put together. To really cement how this works, let's trace through a quick example. Let's run our B C A B C example. At the start, we've counted one A, two B's, and two C's in total. Get the first B. Our stack is empty, so we just add it. We update our remaining count for B. Next is C. C is bigger than B, so it's perfectly alphabetical. We just add it to the stack and update the count. Now, we hit A. We look at the top of our stack, which is C. C is bigger than A. Are there more C's coming later?

[00:04:34]Yes. So we greedily pop C off the stack.

[00:04:37]Our loop continues. Now the top is B. B is also bigger than A. And yes, we have another B coming later. So we pop B off as well. Our stack is now empty. So we push our A. Look at that. By being greedy, we completely replace B and C with A, getting a much better start.

[00:04:55]Next letter is B. B is bigger than A, so we happily add it to the top. Finally, the last letter is C. C is bigger than B, so we add it. A loop ends and our final string is indeed A, B, C. For complexity, our time is order N, where N is the length of the string. Even with the Y loop, each letter is pushed and popped at most once. The space complexity is order one or order 26 because our stack and counting arrays never exceed the size of the alphabet.

[00:05:24]So, what should you learn from this problem? First, monotonic stacks are a brilliant pattern whenever you need to find an optimal ordered subsequence. And second, taking a quick first pass to count frequencies is a great trick for letting your algorithm know what options it has in the future. Moving on, you've probably noticed the AI voice. I built this channel to instantly generate visual breakdowns for my own studying, and I've started sharing them here. I'm testing out this faster, more visual slide format for recent videos because the format is a bit different. Please let me know down in the comments if you prefer this fast-paced visual style or the older textheavy style. And again, drop any questions about the problem logic there, too. All right, as promised, let's look at the solutions for other languages. Remember, you don't need to pause and type these out. Just use the link in the description to copy the exact code from my site, Le Code Unlocked. Here is the full solution translated to Java. Next up, here is the exact same logic written in C++. And finally, here is the solution in JavaScript. Before we wrap up, just a reminder that my main goal is to create a library covering every single leak code problem. If you are studying problems outside of the daily challenge, check out the main channel linked below.

[00:06:34]If you found this breakdown helpful and want to support the channel, consider leaving a tip at buyaba.com/lecode.

[00:06:42]Otherwise, dropping a like and subscribing is completely free and helps out a ton. Keep up the daily coding and I'll catch you in the next