Shortest Common Supersequence - Leetcode 1092 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem shortest common super sequence and this problem is going to be a bit of a pain the main reason that I think it's marked as a hard problem is honestly not because of like how difficult it is I think it really falls into the category of a lot of other subsequence problems so it's like almost identical to all of the other ones but what makes this one hard is that a recursive solution actually does not work even a regular bottom up solution is still not going to work and the main reason for that is because with the recursive solution we're not going to get a time limit exceeded we're actually going to get memory limit exceeded or maybe you'll get both so that kind of tells us that even with the bottomup solution we might get memory limit exceeded so we need to for the bottomup solution apply some space optimizations to it and if what I'm saying right now to you like none of this makes sense I would definitely encourage you to do a little bit of homework before solving this problem learn some dynamic programming I'll show you what specifically you should learn so this is the n code 150 I think you could also do the n code 250 it'll have similar problems but you want to go to the dynamic programming section so there's multiple kind of categories there's like Longs increasing subsequence that falls into like one dimensional DP we specifically want to do the harder one 2D DP so this problem will probably be the most comprehensive for you longest common subsequence but I will tell you that there's actually many other problems that fall into this category as well distinct subsequences edit distance and several more you can like see the solution for longest common subsequence pretty comprehensive every language available for even more you might want to check out uh the advanced algorithms course where I'm not logged in right now but um okay now I am you'll want to go to the LCS pattern in dynamic programming and you'll really want to learn this in depth a lot of like suggested problems you can see like there's at least like five problems I listed here that fall into this pattern but there's honestly a lot more today's problem is also going to fall into this pattern again like the memorization solution you want to have a pretty good understanding of that cuz even that's not going to be enough you want to have a good understanding of the bottom up solution and then to take it even further Beyond you want to go Super Saiyan 3 and then figure out the memory optimized version as well so like I said this is a hard problem for a reason so let's get into it so we're given two strings this is one of them and this is the other one and what we're looking for is to create a new string and the main thing that that new string needs to satisfy is it needs to have both of this and this like both of these strings need to be a subsequence of this one and also we want to choose this string such that the length of it is minimized so just to kind of run through this example real quick the solution is going to be a c a b a c because we can see that a b a c is a subsequence and here cab is also a subsequence they don't necessarily have to be contiguous like in this example they are like this is contiguous and this is contiguous but it didn't have to be like that uh for example we could have had something like this let's say a x a y and then the solution to this would have been maybe possibly a x y because then we can see that this string shows up here this string shows up here and here it is a subsequence if you get rid of this I shouldn't have put an X over it it's literally the character X but anyways you can see that subsequence shows up like this so for this example you're probably thinking well there's actually multiple Solutions isn't there like we could have also done this Y and X and yes you're actually right good observation uh viewer because this is a subsequence and now this is a subsequence as well so what do we do if there's multiple Solutions well it doesn't matter which one we return I think they say that here with multiple Solutions return any of them so I could walk you through like what's the intuition of thinking about this well first we want to kind of just figure out like how do we brute force a problem like this one even that's not trivial to come up with but you really just have to know what this pattern is I'm pretty sure I didn't come up with this pattern by myself the idea is actually simple once you know it though you brute force it like this you keep track of two pointers we're going to solve this with backtracking first then we can apply memorization to it I'm going to go through that relatively quickly because I want to have enough time to cover the uh DP Solution that's going to be really the difficult part but the backtracking and memorization solution will help us arrive at this solution at least logically so we want to sort of backtrack so this first example makes it pretty easy actually because we have this situation where we have a pointer at the beginning here and we have a pointer at the beginning here the easiest case would be like if the two input strings were equal right if we just had like XYZ here and then another XYZ well then we kind of just go through both of the strings and we'd find that they're both equal so the result would just be XYZ so we're going to kind of use that to our advantage because we can do that piecewise as well like character by character we can check okay well these two characters are the same so I'm going to backtrack keeping track of the pointers let's say my pointers are 0 0 right now I'm going to find that they're actually equal so I don't need to make any decision I literally just shift both of the pointers I and J are going to be incremented by one so no decision no branching or anything like that now we're at the sub problem 1 one so now we have a decision to make because now you can see the two characters aren't equal so the question we're really asking is how are we building the string when the two characters were equal we decided that okay well our string is going to have the character a they're both equal it makes sense that we can start with the character a okay but now they're different what do we do well we don't know which character to choose now and I'll put the a down here cuz when we were here we were actually empty but now we could Branch either to uh 2 one so that would mean like let's say the ey pointer is shifted over here or we could shift to one two where the J pointer is then shifted out of bounds we don't know which one of these is going to lead us to the minimal result so we'll try both of them so this was the branch where we chose the character X this was the branch where we chose the character y so let's just consider this Branch for a second when we chose X our ey pointer became out of bounds we still had a character left in the other string we had the character y so we don't really have any choices at this point whether we have one character remaining from this string or we have five characters remaining or more than that it doesn't matter just take all of those and just add them here or like maybe from a base case return them up because there's nothing left for us to choose from the other string so in this case there was just a single character which is y so we would just put y there along this path we would get a x y along the other path it's going to be pretty much the same J is out of bounds we have no characters left from here we have one character left from here which is X if there were more characters we would have taken all of those characters and just returned them there's only one this time though so we just put the X here so along this path we get a YX now recursively from here among these two branches we want to return the minimal well this one was of length two this one was of length two so it doesn't really matter which one we return and so I don't know depending on how we code it up one of these is going to be returned and let's say it's this one a x y now this is very very easy to apply caching to if you're not familiar with caching or memorization or P I'm not sure why you're still watching this video to be honest cuz with all due respect you have no business solving this problem it's just probably too hard for you unless you're like a super genius or something like that so I'm going to go ahead and code this Brute Force solution and then I'm going to add caching to it pretty easy to do that so what I'm going to do is just declare a function I'll call it backtrack you could call it something else just going to take two parameters I and J I'm going to handle the first two base cases where let's say the ey pointer is out of bounds so it equals the boundary which is the length of string one in that case we just return the remaining characters from the other string J tells us where we're at in that string so we can just do this in Python just slice the string so starting from J get the remaining characters now the other case is also similar if J is out of bounds so that's length of string two return the remaining characters from string one starting from I which is the pointer for string one there's one other case it's not a base case though this is actually the recursive case where the two characters are equal now so the character at string one is equal to the character at string 2 if that's the case we call backtrack and this is easy we just increment both of the pointers by one and just return the result of that but think about what this is doing for a second this whole backtracking function we're going to call it like this back track starting at 0 0 and this is meant to return the string so here in this recursive case this is the elegant easy recursive case the two characters were equal so we're running Backtrack on the remaining two strings the remaining portion of the two strings that's the sub problem so that'll tell us the string for the remaining characters but we have to include this character as well I mean we could pick this or we could pick this they're both the same so we'll just take that string one character at indexi concatenate it with the result of this and then that's what we return so so that's not too bad now it's going to get a bit more interesting where we're going to Branch so backtrack this is like the recursive call we could increment I and leave J the same or we could increment J and leave I the same so if we increment I we're saying we chose the character at index I so this will give us the sub problem it'll return us the string of the sub problem but we also want to include the character that we just included so like the character at indexi from string one so we say string one at index I concatenate it with the result of this and similarly down here we chose the character at index J so from string two get that character and concatenate it with the result so among these two we want to figure out which one is minimal so I'll store these in some variables I'll call it Result One and result two because I'm not very creative and so if the length of result one is less than the length of result two then return Result One otherwi wise return result two doesn't matter how you do this like I said if there's a tie it doesn't really matter which one we return so you could add an equal here if you want to it doesn't really matter so this will get us time limit exceeded let me just prove it to you yeah so here you can see we barely get to test case 28 we get time limit exceeded here this is an exponential solution now we can optimize it by adding caching like this I'm just going to use a hashmap and so for this i j is going to map to the string because that's what we're doing here and that's kind of why this problem is hard to optimize the fact that we're actually dealing with strings we're not figuring out the length of the longest or the shortest common super sequence that would be pretty easy to do but we're dealing with strings we have to store those strings in the cache that's going to make this pretty inefficient so even once I add caching which I'll do like this we can check if this sub problem has already been solved if it's in the cache we return like this otherwise we compute the result and right before we return let's throw it into the cache like this or like this and so now this code is going to be more efficient in terms of time we're never going to solve the same sub problem twice so this should be like an N squared solution or really uh terms of memory n * m that would be ignoring though the fact that we're doing string concatenations that's going to make this less efficient I think that will be n * n times like something like uh depending on like the length of each of these strings it could be of length n or M so we can let's say add these two together multiplied by that this is the time complexity I think the memory complexity is going to be similar which is just going to be too much for this problem let me run it yeah so here you can see on Le code we actually get to the last test case 49 but we do get memory limit exceeded so now if you're familiar with backtracking you might know the solution to that memory limit exceeded problem sometimes the bottom up Solutions can allow us to actually save memory let me kind of draw through that solution and then we'll try to code it up in a somewhat similar way to how we coded up this recursive solution okay so now let's get into the bottom up solution I'm going to try my best to explain this but it's not going to be easy I'm not going to lie so let's say we have a string like ABC and we have a string like c a b we create a two-dimensional table that's the way to think about bottom up Solutions like the thought process is not too different from the top down solution so that's kind of why I left some of this here like think about it from the root where we're at 0 0 we're at the beginning of this string and we're at the beginning of this string in this cell what we want to store is like the shortest string that has this entire thing and this entire thing as a subsequence so that's what we want to store here just like how when we start backtracking we want to solve the original problem but for us to do that it's going to depend we kind of saw sometimes if the two characters were equal what we would do is then go down here in this case we would go diagonally and say okay well the result that's going to be here is going to be that character if these two were equal is going to be a plus concatenate a with whatever string we store here so the sub problem and this sub problem of course would be this and this now if that's not the case if this and this are not equal well then we're going to do something similar that we did over here either we're going to go like increase one of the pointers here or we're going to go here so whichever of these two strings is shorter is going to be the one that's concatenated so what is it going to be concatenated to this character or this character well it depends which direction we go so let's say we don't know which one of these two characters to include we include a in which case we go over here the sub problem becomes we have this string and we have this string so we can catenate a with the result of this otherwise we choose this character then we go down here the sub problem is this and uh this so we concatenate C with the result of this sub problem so that's the logic that's how this is going to work I hope that this is enough for you to be able to dry run through this grid if you don't feel like doing it don't worry I'll walk you through it but that doesn't mean you shouldn't be able to do this if you can't do this that's kind of a red flag in my humble opinion now uh before I guess I start walking you through this one thing I want to mention the reason we're doing this uh bottomup solution is because notice from any given position we had like three possibilities we might go diagonal we might go to the right we might go down so notice that for any given cell the entire row like if I wanted to fill this guy in or I want to fill this guy in I go down diagonal or to the right if I want to fill you down diagonal and to the right to fill in any given row all we need is the previous Row in memory we really don't need the entire Grid in memory that's the advantage of the bottom up solution compared to the top down solution and now I'll start filling this in just to make it a little more easy to visualize we noticed that these two characters aren't equal so I'm actually going to go down because that one's going to be a little bit easier so here now we see we're here and we're here these two characters actually are equal that's beautiful so we're going to take a for the remaining part of the string we're going to get that from this diagonal so now we're here we have B and we have B that's great as well they're both the same so to fill in this grid we still don't know what to do but we're going to start with a b and then the remaining we're going to get from the diagonal now things get a little bit interesting I guess this part I didn't mention so maybe this grid actually would have been hard for you to fill in especially if you're a beginner but it's not going to be any different from how we did it in the recursive solution so think about this for a second we're here we have nothing left from the first string but we have at least one character from the other string I mean theoretically we could have ended up over here where we would have had nothing left from either in which case that would have just been like an empty string but this time it's a bit different so now from here we just take all the remaining characters from the uh string over here this time it's just the character C but if there were more we would just take all of those characters so that tells us that first of all now you probably see why I had this grid be initialized a little bit larger than it needed to be because everything that's going to be over here should just be the postfix so this time it's just the character C well what if we ended up over here what would that have told us we have nothing from here but I got something from over here so it would have been B and it would have been the characters that came after it which is just C in this case and over here it would have been a b c similarly over here if we had nothing from this string where over here but we do have something from here it's going to be like this B and over here it's going to be ab and over here it's going to be c a b okay so now you kind of know what's going on over there but finally to get back to what we were doing over here we were looking diagonal and now we know what's going to be over there it's going to be a c so here we fill that in the result over here is b c and that makes sense cuz think about what that actually means it means if you took this string and this string and asked what's the shortest string that we could create such that this is a subsequence of that string and this is a subsequence of that string it looks to me like we found the correct one BC does satisfy that we have that and so now to fill in what we had over here we just take BC and concatenate it over here you notice that not necessarily the entire grid is going to be filled but the way I'm kind of reasoning about this is similar to the recursive solution when we actually fill in this grid we're going to be doing it a little bit differently the way we're actually going to be doing this now is by going row by row so we already know that the last row is going to look like this it's going to have every uh post fix of the original string at least one of the original strings and then for us to fill in this entire row it's going to be pretty straightforward you take this since we're at this row you just take like the last character and put it over there and then these can all be empty initially and then we start filling them in so from here you would look at these two characters see B and C they're different so either go to the right or go below well they're of equal length so it doesn't really matter what we put here let's just put a b from over here I know I already filled the value in but even if we hadn't filled it in we'd still kind of do the same thing we'd see okay B and B they're equal so just go diagonally take B plus C and then we get the string for this okay now I want to fill in this one see how doing it bottom up and I'm doing it in reverse order you actually don't have to do it that way Some people prefer to still fill this in from top to bottom and right left to right but I prefer to follow the semantics of the recursive solution because if we were to change that we were to change the order that we're populating this grid we'd kind of be changing the semantics of the problem it doesn't change the overall result but then you kind of have to think of the problem in reverse order you have to think of it as in like taking the reversal of these two strings which in my opinion is a bit more complicated it adds a little bit more overhead than I prefer so I like to do it this way uh but anyways I'm still filling this in now I'm going to fill in this value over here I look at these two they are different so I look below I see this string of length three I look to the right I see this string of length too so I'm going to prefer this string what that means is if I look to the right I'm basically choosing the A and I'm looking at this sub problem and this these two strings which is going to be BC so I can take a a b c and say that that's the shorter one if I were to go down I'd be saying B plus a c that's still technically satisfies like the subsequence part but it's longer than it needs to be so now we filled in this row now I'm going to fill in this Row from over here I see a and C are different so once again I look down or I look to the right this one is shorter so I can take a plus that and I get AB over here okay so unfortunately I think I might have messed up when I was populating this cell I apologize about that we saw that these two characters were different so what we should have done is like looked below and to the right they're both the same so like I ended up choosing the B what that meant is I took the C and I should concatenate that SE with what I found over here so I really apologize for that sorry you can I guess see that this is actually hard to do on the Fly and recording definitely doesn't make it easier but um now I'm over here let me just redo that part I see these two are different I can look down or I can look to the right they're both of equal length I can pick either one so let's just say I pick the one that's below that means I chose the A and then I have these two characters so I have a c b now I want to fill in this I see these two are different I can either go down or to the right I'm going to choose the one that's below cuz it's shorter so that means I took the A and then I took BC so a b c when I'm over here we already filled that one in but they're equ equal so then we would just go diagonally and that makes sense now finally filling in the last row I'm over here these two are equal so we would then just go diagonally and let's think about what that means for a second they are equal so we're choosing the character C by going diagonally we're saying we want this and this as the sub problem well we just have a string AB left over that's why we hardcoded this outside of here so we would end up with just a c a b over here to are different we look below and look to the right they're of equal length so it doesn't really matter I will go down so I took the C and then I took everything over here which represented this and this as the sub problem I get c a b c finally over here once again they're different I can look to the right or below this one's shorter I get a c and the one that's down here A B C so one valid solution to this problem is going to be this one so I hope this was most of the intuition that you needed the way I'm going to be coding this up is like this I'm only going to be keeping two rows in memory at a time I'm going to start with this one I'm going to call this my previous row I'm going to pick one of the strings and I'm going to take every postfix of it and then initialize an array with all of those postfixes and then lastly over here you could think of that as just the empty string so I'm going to add that as well and then I'm going to have my current arrays do you notice how each of those current arrays even though the first values are going to be empty they're always going to have one string at the end hardcoded and that string is going to be a postfix of the other string so like let's say we have our pointer J which is going to be from right to left we're going to have our pointer I which is going to be from bottom to top depending on where I is that's going to tell us the length of that post fix so here it's going to be that when we move up over here it's going to be AB the last two characters when it moves up over here it's going to be cab the last three characters and so just like that and then we're mainly going to be responsible for filling in these values every single time and then we'll shift these two like this where previous will become this one current will become this one we keep going and then eventually current will be here and we'll fill in everything and then we'll return the value that's here at 0 0 which in terms of the current array is just going to be current at index0 so this way we can save some memory complexity by only keeping a row and memory at a time I think the memory complexity will be something like just picking one of the strings it'll be n and then like the length of these I believe in the worst case are going to be n + m so that's going to be the space complexity the time complexity is still going to be the same as I think the memorization solution n * m * n + m so let's code it up so I guess I'll leave this code here we're going to use like some ideas from it but it's going to be a bit different so first let me just get the dimensions of the two strings because I think we're going to need them a couple times so length of string one and string two now I'm going to initialize that previous array I was talking about in Python it's pretty easy to do so I'm going to do for J in range of M that's going to be the one for string two and that's also why I'm using J I could have used I here but J is going to refer to this string and so every postfix we can get like this starting at at j string two starting at J so the first postfix will be the entire string the next one will remove the first character etc etc so those are all the real postfixes and then one more thing we want to append to this is going to be the empty string and then after that I'm going to set this solution up by saying for I in reversed range of N and for J in reversed range of M you don't have to do it this way but again if you don't you change the semantics of the problem so it becomes drastically different than the previous solution that we coded up if you prefer to do it that way that's perfectly fine I just find it a little bit harder to reason about and I could have showed you that explanation as well but I think the drawing explanation would have been a little bit more uh complicated than it already was anyways inside of here we're going to initialize a current array I'll show you how to do that in a second and then once we're done we're going to return current of zero after every iteration of this loop we're going to switch our or we're going to reassign previous to be the current array and then current is going to be a different array so current can mostly just be empty and this current array is going to be of the same length as the previous array so it's going to be like this um empty string times M and then one last thing we're going to append to this is going to be this current append this string one starting from index I going up until the end of the string so on the first iteration of this loop it's just going to take the last character from string one on the next iteration of the loop it's going to take the last two characters next it's going to take the last three characters so it does exactly what we want it to do and again that's because we're doing this in reverse order so after that we will then um start going through J in reverse order now we're populating this array we're trying to populate this array and the conditions are actually going to be the same as they were in the recursive solution at least pretty similar it's going to be this is the character in string one the same as the character in string two because if they are then we can say current at index J is just going to be we could take either this one or this one they're the same character just take that first character and then get the diagonal how do you get the diagonal well we take the previous row and then we don't look at index J we look at index J + one that gives us the diagonal other wise we have to look either above or below and again this part is actually going to be similar to the recursive solution as well we could take the character from string one so we do this string one at index I then we look below so we say previous at index J or we take the character from string two in which case we look to the right we stay in the current row and we say J + one so the fact that J starts at the End of This Means J plus one could be out of bounds that's the reason why we appended this after all of these this way we'll never get that index out of bounds and we'll also have the correct a postfix so these two I will assign to Result One and result two and then it's going to be pretty similar we're just going to get the length so is this one shorter if so that's great then we can set current of J equal to that otherwise Set current of J equal to result two so I I think that's pretty much the entire code let me go ahead and run this for you and as you can see it does work and it is pretty efficient I guess you could get it like marginally more efficient like twice as efficient and I mean there definitely is a more optimal solution to this problem but the main reason I'm not covering it is not because I can't it's because this video is already long enough I think if you're at the level where you understood everything that I've explained so far you should really be able to figure out that last Solution by yourself or at least like understand the edit tutorial or somebody's like solution in the discuss section at some point I think like these videos or these training wheels as you can consider them aren't really going to serve you at some point you're going to have to figure things out by yourself so I hope at least I was able to help you get this far thanks for watching check out N.O for more I'll see you soon