LeetCode: Longest valid parentheses
Difficulty: Hard
My first hard LeetCode solution!
Start with a subproblem
I started by first considering a subproblem: Given a string of parens and a starting position within that string, what is the longest valid substring of parens that begins from that position?
To approach this subproblem, imagine we are fed a series of parens from an unknown string that may or may not be a valid set of parentheses and we are asked to announce that the unknown string is invalid as soon as we detect that it cannot be valid. What could we observe that would guarantee that the complete string is going to be invalid no matter what remaining parens are produced?
Well, if the first character is a closing paren, we will instantly know that the sequence of parens can never add up to a valid set of parentheses. In a valid set of parentheses, every closing paren is preceded by an opening paren. We can generalize this: if we tally the number of open and closing parens we have received, if we ever count more closing parens than open parens, we know the unknown string is invalid because there are closing parens that will never have matching open parens.
Also note that if we reach the end of the sequence and our tallies of open and closing parens are not equal, we know the string is invalid because every open paren must be matched with exactly one close paren. On the other hand, if we reach the end of the sequence and there has always been at least as many open parens as closing parens, and there are exactly the same number of open and closing parens, we can be certain that the string is valid.
A little simplification we can make at this point is to note that we don't actually need to keep counts of the open and close parens. It will suffice to use a single counter that starts at 0. If we increment it every time we see an open paren and decrement it every time we see a close paren, we will always know if we have more open parens or close parens, or if they are equal.
Generalize from the subproblem
So now we can start from index 0 and move along the string, using a counter to ensure we always have more open parens than close parens, and tracking the length of the current substring with another counter. If our counter ever goes negative, that marks the end of that substring. We can reset our counters and continue with the next character.
def longestValidParentheses(s: str) -> int:
parity = 0
curlen = 0
longest = 0
for char in s:
curlen += 1
if char == '(':
parity += 1
if char == ')':
parity -= 1
if parity == 0:
if curlen > longest:
longest = curlen
elif parity < 0:
curlen = 0
parity = 0
return longest
Now what does this give us? It's tempting to think we're done. I thought so, initially.
But let's think about the scenarios where this will give us the length of the longest valid substring (LVS). The LVS may be immediately preceded by nothing (if it's at the very beginning of the string), by a closing paren that does not have a matching opening paren (if it had a matching paren, it would have to be part of the LVS since it's adjacent to the LVS), or by an opening paren that does not have a matching closing paren (see previous parenthetical). In the first case, when we reach the beginning of the LVS, our counter will be at zero. In the second case, our counter will also be at zero, since we reset it every time it goes negative. But in the third case, our counter will be greater than or equal to one (depending on how many unmatched open parens there are), and so we will not detect the LVS. We will instead reach the end of the LVS with our counter never going below one.
To handle this last case, what if we proceeded in the same way with our algorithm, but started from the end of the string to look for the LVS in case we missed it on our first pass the other way. Coming from the other side, we can consider the same three cases: The LVS may occur at the end of the string, it may be immediately followed by an opening paren, or it may be immediately followed by a closing paren. The first two cases are exactly the same as before; they pose no problem for us. We only need to consider the final case now. In particular, we only care about the final case if the first pass failed to detect the LVS, and that only happens if the LVS is immediately preceded by an opening paren. But if the LVS is immediately preceeded by an opening paren and it is immediately followed by a closing paren, those parens in fact match, and are actually part of the LVS. Thus we can be confident we will always identify the LVS in one of the two passes.
Final solution:
class Solution:
def longestValidParentheses(self, s: str) -> int:
parity = 0
curlen = 0
longest = 0
for char in s:
curlen += 1
if char == '(':
parity += 1
if char == ')':
parity -= 1
if parity == 0:
if curlen > longest:
longest = curlen
elif parity < 0:
curlen = 0
parity = 0
parity = 0
curlen = 0
for char in reversed(s):
curlen += 1
if char == ')':
parity += 1
if char == '(':
parity -= 1
if parity == 0:
if curlen > longest:
longest = curlen
elif parity < 0:
curlen = 0
parity = 0
return longest
Space and time complexity
The space complexity is O(n) to hold the string itself.
The time complexity is O(n), as well. We complete work twice for each character in the string and O(2n) = O(n).
Other solutions
Looking at other solutions on LeetCode, there are a few approaches that avoid making multiple passes, so this is certainly not optimal.