Daily Leetcode : Jul 19, 2026 - 1081. Smallest Subsequence of Distinct Characters

[00:00:01]Hey, hey everybody. This is Larry. This is day 19 of the legal day challenge.

[00:00:07]Hit the like button, hit the subscribe button, join me on Discord. Let me know what you think about today's prom. Uh yeah. Uh in New York, it's still crazy air today. Didn't do that much. Watch the third place game a little bit. I mean, it's a third place game. Um I don't know. People call it exciting, but let me know in the comments if you find it exciting. I mean, I just like it's just like watching the Allstar game, right? Like in NBA or something, you know, like everyone score. There's a lot of scoring. That doesn't make it exciting. It's just a lot of scoring. I don't know. But in any case, uh it, you know, doesn't matter. So, tomorrow will be fun. Uh let me know in, you know, I mean, I've been talking about the World Cup the entire time, so final comments. Let me know in the comments uh who you rooting for, who you think will win. May not be the same team, but you know, only two left. Uh yeah, and I I ran like four miles way easy. It was pouring. The weather was po uh the air is poor and it was pouring.

[00:01:04]So I don't know uh but it's been a tough week for running. But let's take a look at today. We have 1080 one small subsequence of distinct characters.

[00:01:14]Given a string S, return, we turn the lexographically smallest subsequence of S that contains all the distinct characters of S exactly once. That's really weird, but I mean it's fine.

[00:01:27]Um I mean I think there there's actually like um I was going to say there is probably um uh uh I mean what I was going to say is that n is a thousand and n is equal to th00and is pretty easy, right? Because there's n square substrings uh n choose two substrings if you want to be more precise and you know that's fine. But the the thing that um and I'm already kind of jumping ahead in my mind of how would you solve it if it's big?

[00:01:58]The the best answer is probably uh um suffix away. But um but I think you can actually probably no I think suffix array is probably still the best answer. um and probably something variation of it. I don't know if you can just directly do suffix away um because of the unique the distinct characters part. Um h it is kind of tricky. I I actually don't know. [snorts] Um but n square one seems pretty okay, right?

[00:02:44]Um and um yeah, I mean I think that that's really it. The key thing to note is that you have to be smart, right? Because and I and this may be fast enough just because it's Python, but uh or you know kind of thing where you do something like this, but then if you do something like if I don't know if you do a loop, right? So a loop could be like if unique and that's not a real function maybe right from start to end um then you know dot dot dot dot dot or if this is actually the unique part is f of one and then you do a comparison of you know maybe best is less than this this thing right even just doing this comparison technically you would do it character by character and we do it character by character this is n cube already right even though it might not look that way because it's an if statement Um cuz this one you could do all one easily for unique, right? Just make sure there's no dupes. But this part and we're not smart about it. This could be N cube, right? Um Oh, I'm actually messing this up. Am I?

[00:04:05]No. No. No. Huh?

[00:04:08]Okay. No. No, no. So I I Okay, I actually messed this one up a little bit. I mean, what I said is true, but I just realized that this is not what the poem was asking. That's why I got that's why I paused and got a little confused cuz it's not that all the characters or subsequence was unique cuz I was like, wait, if it's lexographically sub small and it's just one character, right? So that's why I was like, wait, that's not right. So I had to reread it and when I reread it, I was like, oh, no, no, it's it has to contain all the distinct characters. then that's that's easier because that is just sliding windows and everything I said is kind of a lie. I mean it's kind of true but also not like it's not a full lie but it's just not as relevant as I was hoping it would be. is just that it is sliding window, right?

[00:04:51]Because you know how many distinct characters there are and if you know how many distinct characters you are, then you know what your window is, right? So that's basically it, right? So maybe write something like um C is equal length of set of S, right?

[00:05:07]Um and then now just do a sliding window, right? So left is equal to you could do something like this. um where left is equal to right minus C + one right there there are a lot of ways to write sliding windows some days I like to play around with it but the idea being that okay you have F's a collection right a calendar rather sorry um and then now you do f of right um or f of s of right increase by one f of s of left.

[00:05:47]Uh the way that I did it, this is actually the inclusive one. So f of left minus one uh subtract by one. And because sometimes I like to write it this way because it becomes very obvious that well this has to be greater than than one, right?

[00:06:03]Or it has to be greater than zero otherwise it's just out of bounds and it would make no sense. Um and then you know you can also do or you have to anyway do something like if then you delete it right. Um and then the other thing is that now if left is greater than zero then now you don't have to worry about because I always get confused about plus one minus one or whatever one here but now if the left is greater than zero that means that left is inbound and right is inbound then the entire subsequence is inbound. Wait is it subsequence as maybe I confused myself. Oh it is subsequence. I am.

[00:06:39]Huh.

[00:06:41]They didn't make it. Okay. They usually I guess maybe that's like a newer thing where they usually describe subsequence.

[00:06:47]But I again I confuse subsequence with subway. So there's a lot of reading issues in me tonight. I'm going to drink some water to hydrate because maybe that'll help me not be so dumb. Um but this would be I mean I'm almost there anyway in terms of sub window, right? Um or sub array but we'll do subsequence.

[00:07:05]So basically we sol we're solving three problems today. A lot of bonus solving for for y'all at home to watch but uh but subsequence right.

[00:07:31]Okay. Um that means that you have to go see time still. The idea being that how would I say this?

[00:07:50]I mean when whenever you do um not all the time but very often when you do like a lesser graphically smallest thing you're you're you're trying to do this right where you go um is there an A? Oh sorry can A be the first character? Can B be the well if A is the answer to A is no then you ask if it's B right and then now here is let's say there's A then you go can it be B no can it be C right and then the last one is fill in right and and the and the hard part comes from um or the I don't know it's hard heart but the part comes from uh whether you are able to um to to or like the the the thing I said like can the first character be Right?

[00:08:34]Well, what does it mean for first character to be able to be A? Well, the first character being able to be A means that all the characters after the first character, right? Um it still contains um it still contains all the characters that you need, right? In this case, um because you still need a B and a C, everything after A still contains B and C and so forth. So, that's kind of the the first idea, right? And probably that's the only idea really. I mean after that it just becomes of like how do you do it right? So here we go. Um so then and the idea of course actually well I was going to write something really like fine but actually I will take off. I mean maybe the other one is a little bit harder the 316 one but and there is a a a better way to do it and I would urge you after we solve this to obsolve it.

[00:09:33]Right. But for me, for now, then all we have to do is just go um right like we just literally go. Okay.

[00:09:44]So, for one character at a time, right? And maybe we have like a done thing to to kind of keep track of where we finished. Um again we go um maybe maybe this is like uh I don't know why I'm bad but yeah uh I'm trying to name things that's why maybe alpha for alphabet is you go to set of this but let's make this a list and we sort it right and then see is alpha, right? So then now we can go okay well for is this I mean this is fine I think this is is it's awkward but fine right then now we could do an I in range of C can alpha sub I be used right and this is already sorted so yeah be used next right and then here maybe we have like a marker on um the last index we used right so here um so if done or if I and done then we're just done anyway right so continue otherwise now we go well can it go right well we start from last last one used plus one maybe or maybe you could go to zero depending on you know whatever but uh for J and range from last plus one all the way to N Right. Um so alpha i can be used if if we found the next iteration the next appearance of alpha sub i right and by definition because if it's not done then it has to be in there we just have to find it right. So yeah. So we go if so there two you can write if this of like an FSA like a state machine. There must be a cleaner way to write this. I feel like I'm just writing crazy crazy thing now but uh it's equal to um S of J and this is good and then we found and then we break right. So yeah well well no we say it's a state machine right? So there two things one is that find first right uh and then uh and then the rest is um I feel like I'm not writing this way very very well it probably could be why am I doing this I think I'm just a little bit like I don't know anyway yeah uh the now found is equal to true Right?

[00:12:47]Just go found right if not found and this is is found is equal to true we continue to the next one right. Um otherwise if found then uh yeah then if s of j and actually let's contain alpha subi.

[00:13:14]So we could do if S of J is not in done right.

[00:13:22]Uh so found uh so maybe called rest is equal to set right west add s of j right um and of course it also had you know and s of j is not equal to alpha subi because that would just be confusing but yeah west sub add is equal to s of you can just remove it I guess um yeah right so that's basically it that's the state machine that we found the first instance of the character and then after that if it's found then we just kind of get see if the rest of the characters are in there right so if length of rest is equal to actually uh maybe this should have been a thing because that's how many things we've done and it's C because we're trying to construct an answer of length C this is just iterating it right? So maybe we have an answer and then maybe this is uh I don't know naming things is hard let's call it K right so if the length of the rest is equal to C minus K uh minus one for the alpha then we are good otherwise then yeah if it's not good then we just contain it.

[00:14:52]Right? So then if it's good then now answer that append alpha subi and then we break right uh and then maybe we do another um [sighs and gasps] found index is equal to true or something right. This is very bad code actually. But it also shows you that like there's so many ways to do this even poor ways apparently right uh if found index or if not found index. Uh oh. I I I guess I was actually putting a thing where like you know then maybe return negative one but I guess that that's not possible because by definition there will always be a character that um contains all the other ones because that's just the next character, right?

[00:15:51]Like like um like alpha sub I would be.

[00:15:54]You go do all that stuff. Okay. So maybe that's fine. But we also update last is you go to I, right? So that we don't uh no no not I is equal to um it's equal to this index actually but um and yeah and then we can just return right and that's really it. The worst code ever. Um, apparently I forgot to add stuff to done as well. Um, so done.

[00:16:33]Add alpha survive.

[00:16:39]I mean, it's it's uh hopefully this is this works. Yep. But this is very ugly obviously. But also, you know, maybe that's a a good point of practice, right? which is that you could do a lot of crappy things and it still kind of works if you have the algorithmic uh if you practice enough and algorithm is kind of right right you don't have to be super precise but um but again you know there are definitely ways to better than this this is C^ 2 * N which is probably too uh not super fast c is up to 26 so that's already like two what is that I don't know what 26 square is right but uh times N what What did I do last time? Uh, oh yeah, that's what I was wanting to do actually. Um, keep track of the index and binary search. But it is the same idea though. Um, except for here instead of binary search, I just did a linear search.

[00:17:36]There are probably better ways to do it though. But but uh yeah, that's it. That's all I have for this one. Let me know what you think. This is going to be c ^ 2 * n which is 26 2 * n00.

[00:17:52]But uh yeah, thanks for watching everybody. This is a messy video. Sub three different things, but uh yeah, stay good, stay healthy, good mental health. I'll see y'all later. Take care.

[00:18:02]Bye-bye.