Reverse Substrings Between Each Pair of Parentheses - Leetcode 1190 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem reverse substrings between each pair of parentheses so this is a really really interesting problem I'm going to go over two solutions actually so the first one is going to be an N SED solution and an n space well I guess this is the time complexity this is the space complexity this one actually does get passed on leak code and this is the one I was actually able to come up with now the second one to be honest I did not come up with myself it is a linear your time solution and quite frankly I think it's going to blow your mind I've never seen an algorithm like this one but it's not super complicated and it makes a lot of sense when I had my first solution pass I thought that was the best one but it turns out there is a better one I don't know if I would have been able to come up with this one by myself even if I had tried just to be honest but okay let's get into it so consider this example we have an opening parentheses here another one here then a closing one and then another Closing one what we want to do is take the innermost string in terms of like parentheses and reverse it so it would look uh something like this and then we kind of get rid of the parentheses so now imagine that our string looks something like this not a great drawing so sorry about that but then we take that string and then reverse that so think about it I is going to go over here you is going to go over here and then we're going to take the inner portion and reverse it again a second time so now now it's going to be I love you and uh don't take that too personally just kidding so the idea is that some portions of the string are actually going to get reversed multiple times and also we want to reverse portions separately so like first just the inner Portion by itself and then combine it with the other portion and then reverse that entire thing and you can imagine it could go deeper we could have deeper levels of nesting like maybe there were some parentheses here and we'd reverse this then reverse the whole thing and then reverse this whole thing and before you even start to brainstorm some solutions let me give you a counter example to possibly a solution you're about to come up with we see that this kind of part that's in the outermost parentheses is separate the U is over here the I is over here does it really have to be like that what about this like AB I guess and then I put a c over here just that or maybe c d what would happen with this we'd reverse this get ba a and now we have b a c d so maybe something like this and then we reverse that whole thing we get d c a b so if you're thinking something like a two-pointer approach maybe where you reverse this and this well forget about it it's not going to work cuz if there was nothing here why would we want to swap a character like from the inner portion with this we wouldn't I thought that part what I just said didn't make a lot of sense so I got an example for you this is what I was talking about take a look here the output is this now imagine you try to do the twooter approach I just mentioned we have a pointer here and a pointer here getting to the first character for each a is here f is here obviously this one is more nested than the other one so what do we do swap them okay we'll get an F here and an a over here but again I think like now you kind of realize it's not going to work because already like you see that the string does not end with an a here so that's what kind of made me realize that there might not be a shortcut that we do kind of have to in a sense Brute Force this and what do we know about parentheses well if if you've solved any of the other kind of common parentheses problems you know that a stack is almost always useful like that's the only way we can kind of keep track of this portion being separate like this is Within These two parentheses and then the amazing thing about a stack is that it allows us to reverse very easily and I kind of just know that off the top of my head cuz I've used Stacks quite a bit but I'm going to walk you through why a stack is going to help us here so we're going to run sort of a simulation we're going to go character by character and push them onto the top of our stack including uh the open parentheses so right now our stack might look something like this open parentheses I get a u and then I'm going to move from here to the next position so I'm going to get another open parentheses I'm really sorry if these look like the C character that's not what they are they're parentheses okay maybe that's a little better now we're going to go through these characters notice how all we're doing is just taking all of these and pushing them onto the stack that's usually what you do with parentheses style problems because it's not until we reach the closing parentheses that we realize we have a complete portion and we want to take this portion and reverse it imagine if we tried to reverse it before we reach the end of it we try to reverse this what would we end up with something awful that's not what we want so wait until you reach the closing parentheses okay once you get there like once we get to this we have this on the stack and then we reach the closing parentheses what are we going to do well we want this portion how do we get that portion keep popping until you get back to the open parentheses so what we're going to do pop first pop second pop third pop fourth so what we're going to end up with imagine we take those and store them in some kind of a list in the order that we pop them we pop that guy first so we get e pop that second get v o l so we end up with this and imagine this is in some kind of a list notice how it's rever versed that's the neat thing about a stack you pop from the stack and you'll end up with the stack in reverse order great so now what do we do well do we just take this add it back to the stack pretty much but we should probably get rid of the open parentheses there and watch what happens when we do that exactly what we want so I'm going to pop that as well and now I'm going to push onto the sack e v l and so imagine this is just not even here we have this port portion and so that's amazing because now we've kind of taken this and concatenated it with the stuff that came before it and it could have been that nothing came before it that's perfectly fine right it'll work the same either way so now we're going to do the exact same thing we have our pointer here we did what we wanted to do our stack is in good shape now keep going until you reach the next closing parenthesis we got I over here add that we got closing over here time for the fun part I'm going to kind of cross this out but now we're going to pop first second third fourth fifth and we know that the order that they're going to end up in is something like this I love and again we're going to keep going until we reach the open parentheses We Got U over here add that finally the closing parentheses we remove that right we just get rid of it so everything has been popped from the stack we're going to take this and now add all of this to the stack so by the end it our stack will pretty much just look like this and what do we want to do with all these characters pretty much just combine them so we can turn them into a single string in O of n time I'll show you how to do that in Python but that's the general algorithm now it might have looked like it was a linear time algorithm but keep in mind it's not it's going to be in the worst case N squared to be a bit more precise it's going to be Big O of n where n is the the length of the input times M where m is the number of pairs of parentheses and this one probably explains to you why the time complexity is like that anyway because we're going to go through each portion and reverse it right it's the simulation that I was talking about this is reversed then this entire thing is reversed if there was another matching pair that would be reversed as well so however you want to slice it this is the worst case this is a bit more precise space complex is also o n obviously because of the stack let's code this up okay so now let's start coding it up I'm going to initialize my empty stack I'm going to go through each character in the input string s two main cases where we care about if the character is a closing parentheses we're going to do some stuff otherwise it's the simple case whether it's an open parentheses or an actual character we don't really care just go ahead and add it to the stack that's all we care about now for the fun part up here what did I say we were going to do I said we were going to now keep popping until we reach the open parentheses and then pop one more time so the easy way I think to cat it up is kind of like this if the top of the stack is uh not equal to the open parentheses just yet start popping from the stack with this Loop right now as it is we will leave the open parthey on the stack so after all of that is done we want to pop one more time out here to actually get rid of that open parentheses now the reason I'm putting that out here and not in here is because in here are the actual characters that we want we are going to save those I'm going to call it portion you can call it something else to this portion we want all these characters to be added to it in the order that they were popped so just something like this portion do append that character that happened to be popped and so now we want to take all the characters from this and add add them to the stack we could do that with a loop but thankfully python has a neat little shortcut like this extend that portion so this will pretty much do what I said earlier it'll go through all the values in here and push them onto the stack so it's kind of like a pend except instead of accepting a single value it accepts a list of values that's pretty much it what do we do at the end we don't return the result because it's a list or stack we want to return a string so let's join all the substrings in the stack we can do that like this in Python take an empty string use it as the delimiter and then join all the strings in the result so this is the entire solution let's run it I'm very unintelligent today so we don't have a result variable today I'm pretty used to that so we should actually replace this with stack let me try again and now you can see it works and wow it's at 98% so you can see why why I thought that this solution was efficient that this was the most optimal one but it turns out there is a better one in terms of Big O time complexity quickly before I show you that I just want to say if you're interested in learning more about Python and these sorts of tips and tricks about it and knowing like the time complexities of each operation I'm actually working on a python for coding interviews course it'll be a fully interactive one just like this python for beginners pretty much it'll be like little documentation lessons it's kind of like an interactive textbook where you can like practice each time you learn something new if you're a neat code Pro member you'll automatically have access to this when it comes out okay so now we're going to get into the second solution I really want you to try to be able to come up with it by yourself so I'm actually going to run like the simulation and maybe if you're good you can convert that simulation into the code and probably learn something new from doing that but if not that's perfectly fine because quite frankly it is a very tricky algorithm to come up with even though it's simple it kind of blows your mind cuz it's like wow I would have never thought of that so let me show you what the solution is but first notice something we saw that this portion got reversed once and then it got reversed a second time the outer portion got reversed once consider a different example like this one like maybe a b c I'm just adding random characters this is one layer deeper so this layer will get reversed once and then it'll get reversed twice and then it'll get reversed a third time so it'll get reversed however many times it was like nested the portion out here will get reversed twice the outermost portion will get reversed once so in a sense the outer portion is always reversed that's not like a huge hint or anything but it's just an observation I think that will help you understand the solution I'm about to show you right now because what we're going to do is anytime we see a parentheses we're automatically going to go to the other one so we start at the beginning here but we know that this open parentheses has a matching Closing one so I'm going to go over there so I was here I'm going to leave a little blue Mark just to show you I was here but now I'm here and now we can't really go in that direction we're going to go in the other direction we're going to alternate so now I'm going to arrive at I I'm going to have my result output here and I'm going to put I there and that does make sense because we don't really know how many times we're going to end up reversing this portion just yet we don't know how deep it is just yet but we know that the last character before the parentheses here if there is a character it's always going to go at the beginning cuz the outermost portion is only going to be reversed a single time so it does make sense now we're going to go here it's a closing parentheses so anytime we see a closing parthey we automatically go to the matching open parentheses here and Alternate Direction so now we're going to start moving to the right now we're going to go character by character adding them to the result so this time we're only adding characters to the result we're ignoring the parentheses so we add L we add o v e uh go through all of these and then once again we do arrive at the closing parentheses over here so once again we're going to go to the open matching preny we were already here though so are we starting to do repeated work no because now we're here again but the direction is going to be different our direction is going to go the other way now we're at you and so now we're going to add that to the result and this is it this is the result sorry I had to redraw it but just to finish up our simulation we were at the U we're going in this direction we're going to be back finally at the beginning at the open parentheses but right now our direction is going in this way so now when we go to the closing parentheses at the end our direction is going to be in this way so now we will increment and now we reach out of bounds so that's how you know that we're done isn't that such an elegant solution so I think probably the biggest question you might have at this point is why does this solution work like forget about even being able to come up with this by yourself but why why exactly does this even work well think of it this way we start at the outermost layer and we move inwards even though we teleport from one end to the other we still move inwards we know that the outermost layer should be in reverse order so of course we're going to start at that character okay and then we're going to keep either getting characters which is fine or we're going to reach a parentheses now going this way you're not going to expect to see a closing parentheses that would be invalid right like if there was a closing parentheses here that'd be invalid the parentheses are guaranteed to be balanced so if we reach an open parentheses we stay inside of that portion we will teleport to the other side the open parentheses so that we can then reverse this portion but we will stay inside that portion so it turns out that it's all about the direction that we Traverse each portion and if we start out like this if start out going in this Direction that's fine because we know we're going to get to the end anyway but for a particular inner portion we don't know should we go through this from left to right or should we go through this from right to left well that's why we maintain the direction because it's alternating think of this that string I showed you earlier which could be arbitrarily deep in terms of nesting like this remember how I said this one gets reversed three times this one gets reversed two times this one gets reversed once isn't that the same as saying this one gets reversed three moded by two times so only a single time this one gets reversed two times so it's pretty much like it got reversed zero times this one got reversed once so yeah that's fine this sort of tells us the Direction with the approach that I explained earlier this portion will end up being traversed in reverse order this portion will end up being traversed in order and the outermost most will always be traversed from right to left now I think this is some of the intuition where you can begin to understand this solution which is a very good start if your goal is to be able to come up with a solution like this one on your own that's a very ambitious goal and quite frankly if all you're trying to do is pass an interview I don't think it's worth pursuing that goal okay I'm editing this in after the fact but this is some intuition you could use to actually come up with the optimal Solution by yourself just focus on the output for a second not notice how we have one portion here j i and that portion is here obviously it's in reverse order next we have a second portion GH and that portion here is going the other direction and then next we have the portion Fe that portion here is obviously going the other way in the output lastly CD well not lastly sorry it's here it's going in order and then here ba it's going the other way so basically the tldr is that you can come up with these solutions by thinking of creative examples and that's something I think I've talked about on this channel before you can see this is kind of going in reverse order but each section is not necessarily being traversed like in that direction right like that's kind of the complicated part the direction is the thing that's changing so this is again just some intuition in summary you can kind of tell based on the simulation that this is going to be an O of n algorithm and in terms of just maintaining the space like the output that is also o of n if you count that and the way we're going to be building it you kind of have to count it cuz we're going to have it in an array and then we're going to convert it into a string now we're actually going to code it up and I didn't really explain fully I think in the drawing explanation how to code it up but that's the fun part we want to be able to teleport right so I'm going to first just try to implement the algorithm I'm going to start my pointer I at the beginning and I'm going to have my direction initially set to one this is basically how much we want increment I by right now it's one so obviously we're just going to be incrementing it by one moving to the right but sometimes we're going to set it to negative one that's just an easier way of handling this than like we could like hypothetically set this to a Boolean like true is for right false is for moving to the left and then we could have some kind of if statement like if direction is true then maybe increment I by one like that would work it would just take a little bit more code so I think having the direction be a number is just a concise way to do it we're going to also maintain our result which is going to be a list and then when we return it we're going to do something like this dot join everything in result so now for actually running it we're going to do something like this while I is still in bounds there's two cases this time only two cases either this is a parentheses the character at I is a parentheses it could be open or it could be closed or the other case is it's not it's an actual character that that's the simple case I'll do it first append to the result the character at index I what about this case well we're at index I either we saw an open parentheses or a closing one well what do we want to do well we want to teleport our pointer we want to shift this pointer all the way to the other matching parentheses we want all matching pairs of parentheses but we don't really have that information to get to the other side would be an O of n oper right if we're going to iterate over the entire string to get to that matching parentheses it's not going to be efficient so we do some pre-processing we do some pre-work some computations we're going to compute all pairs all matching Pairs and we can't do this with a left and right pointer technique as you might be tempted to because consider this example something that looks like this I don't even know if this is a valid example in the context of this problem but if you had a left pointer here and a right pointer here you'd say okay these are matching pairs then you'd go inner you'd have a left pointer here and a right pointer here you'd say these are matching pairs but that's not correct so that's why we can't do two-pointer approach we are going to stick to the stack approach so I'm going to do something like this for I C in enumerate the input string and by the way if you don't know what enumerate is this is also something I'm going to teach in the python for coding interviews course and pretty much all the stuff you see here will be covered and next we're going to do something like this either the character is an open parentheses in which case we're going to append not it to the stack not the character but actually the index because we want all matching Pairs and if we want to down here be able to move from one index or one parentheses to the other we need the indexes of those parentheses so up here we're going to have this uh stack do append the index I that's if it's an open parentheses we're looking for matching pairs though So eventually we will find a closing parentheses and we know that closing parentheses only close the most recent open parentheses and thankfully we're keeping track of the most recent open parentheses on the stack so a closing parentheses tells us we can now pop from the stack so stack.pop and this will uh give us the index of the open parenthesis so let's save that here so right now my J pointer is at the closing parentheses my I pointer so right now my J pointer is at the open parentheses that we just popped my I pointer is at the closing parentheses and so what we want to do is just map them that's why I created this hashmap up here to map I to J so this will be set to J and the opposite will U also be true so J will be mapped to I so it's kind of like an edge in a graph if you think about it an undirected edge like this maps to that this maps to that okay so we're almost done this was just a little bit of pre-processing so that we could finish this part in linear time and now I'm going to show you how you can do that when you're at a parentheses go to the other matching one so just take our ey pointer and reassign it to pair at index I but that's not enough remember every time we teleport or we like switch parentheses we change the direction as well so in most languages you can do something like this multiply this by 1 multiply the direction by negtive one python is such a beautiful language though that you can actually do this where you set it to negative of that that's why python is considered pseudo code by many including me um we're almost done now you might be able to see which line we're missing this is stuck in an infinite Loop currently so what should we do well down here we want to shift the pointer we're not going to do plus one we're going to do plus the direction it could be positive or negative but it will tell us the correct direction to move in so this is the entire code again if I were you I wouldn't feel bad if I wasn't able to come up with it I didn't either and I'm personally just excited to learn about something so interesting like this anyway just to keep your brain sharp and just to kind of appreciate like the beauty of algorithms but this is the final code you can see here it works it's pretty efficient but somehow it's actually less efficient than the previous one kind of funny but if you're prepar in for coding interview check out n code. if you want to thanks for watching and I'll see you soon