Maximum Nesting Depth of the Parentheses - Leetcode 1614 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem maximum nesting depth of parentheses we're given a string and basically a really really long description here ain't nobody got time to read all of that so I'm going to quickly summarize it they Define something called a valid parentheses string which is pretty much what you would expect when you have parentheses You' expect every open parentheses to be matched with a closing parentheses now we could technically also just have like an empty string or we could have a string with a single character so they say these empty strings or just a single character are valid they don't explicitly tell you this here but if we had multiple characters a b c we intuitively know that this is valid now the way they told us that this is also valid is with a kind of an over complicated definition but I guess this is very mathematical in nature what they said is any valid strings concatenated with each other are also valid so when you think about it each of these is an individual valid string so if you add them all together they are also valid if you take any valid string like this and wrap it in parentheses it is also now valid now what we want to do is calculate the depth of this valid parentheses string we don't have to worry about validating it it's not like the problem leak code 20 valid parentheses it's actually much more simple than that because first of all we're only dealing with this type of parentheses we don't have brackets we don't have curly braces this is going to be very simple for us now in in terms of what the depth is again it's pretty much what you would expect so if we have like a string like this with just one open and one closing parentheses it has a depth of one if you have a string like this where open and close open and close this also has a depth of one you can think about how nested is the parentheses now if we were to move these such that it's kind of double nested this has a depth of two so just by kind of what I showed you right now you might have recogniz the pattern you might have recognized what the solution to this problem is basically how many consecutive open parentheses do we have before they are closed like if we go through this string from left to right we see open parentheses okay that's a one okay two open parentheses we have now two open parentheses that haven't been closed now we might see some contents in between here we might have seen some contents over here or here it really doesn't matter ignore every character that is not an open parentheses or is not a closing parenthesis at this point we see that okay this is a closing one so we had two now we decrement that by one now we see another one and it's a closing parentheses decrement that by one and we should always end up with zero because we're pretty much told that this is always going to be valid so again we're not worried about validating this we are just worried about as we scan from left to right we want to know what was the maximum number number of open parentheses that we were able to find before they ended up being closed quickly looking at this first example I've just gone ahead and blown it up but it's kind of meant to confuse you just like all of this it's more simple than it seems we see open parentheses here okay our count is one we see some characters we ignore them who cares what they are we already assume everything here is technically valid first of all this is valid so then we see another open parentheses okay now our count is at two we see some characters closing parentheses so count goes down to one and then we see an open parentheses and then another open parentheses so then our count goes up to three basically that means that at this point the depth of the nesting is three and that makes sense because these two parentheses kind of negate each other so we had one we're in one layer of nesting then we see two open parentheses so this is three layers in and then of course it gets closed by this one so then our count goes down to two closed again down to one closed again down to zero but the maximum among everything we saw was definitely three so three is what we return and you can see that's the correct return value here so straightforward problem we can just iterate in O of n time iterating over the string don't need a stack don't need any data structure this is constant space let's code it up so first I'm just going to initialize a couple variables one is going to be the result that's going to be what we end up returning that's going to store the max depth now we're going to have another variable we could call it Cur or count or whatever it's going to be the current depth of where we're at in the input string so the way I'm going to iterate over the string is actually very simple just for every character in the string we don't need to worry about the index of any of those characters we only care about two specific cases is it the open parentheses or is it the closing parentheses so like this and you can probably guess what I'm going to put in each each of these if it's open we increment the count by one if it's closing we decrement the count by one now regardless of what we ended up with we want to know among every position in the string which one led us to the maximum and what was that maximum we don't really care about the position but what the maximum depth was so down here we can always update the result like this always taking the max of itself with whatever the current depth happens to be and so this is the whole code let's run it to make sure that works as you can see it does and it is pretty efficient if you're preparing for coding interviews check out NE code. thanks for watching and I'll see you soon