Solution with discussion https://discuss.leetcode.com/topic/75978/python-solution-with-detailed-explanation
Brute Force - O(N^2)
- Find the longest valid run from every starting index from 0 to N-1.
- To find the longest run, push "(" on the stack.
- When you get a ")" and stack is empty, break. We have hit an invalid string and future characters cannot make it valid.
- Otherwise, pop "(" and increment so_far count by 2. If after popping, stack is empty, then we are sure that we have a valid sequence so far. If the stack is not empty, we can still have a valid sequence depending on future characters. Example "(()" - starting at 0, invalid sequence.
- Another Example: "()(())" - at index 1, we have so_far as 2 and valid sequence as 2. Now imagine index 4. We pop and make so_far as 4. But stack still has "(" from index 2.
class Solution(object): def get_max_run(self, start, s): st, so_far, valid_so_far = , 0, 0 for i in range(start, len(s)): if s[i] == ")" and (len(st) == 0): break elif s[i] == ")" and st[-1] == "(": so_far = so_far + 2 st.pop() valid_so_far = so_far if len(st) == 0 else valid_so_far else: st.append(s[i]) return valid_so_far def longestValidParentheses(self, s): """ :type s: str :rtype: int """ max_so_far = 0 for i in range(len(s)): max_so_far = max(max_so_far, self.get_max_run(i, s)) return max_so_far
Linear Time Solution
- Scan the string. If character is ")" and top of stack is "(", pop the stack and move ahead. You found a match.
- Otherwise just push the character to the stack. Note this could be either ")" or "(".
- The big insight is that the characters between the indices that are left in the stack constitute valid parenthesis. You just need to scan the remaining stack to find the largest run.
- So for a string of length 10, say the stack had [3, 6], this means valid runs of [0,2], [4,5], [7,9]. If the stack were empty, entire string was valid.
- We need add two markers -1 (to indicate the start) and len(s) to indicate the end. Otherwise an example like "()" will error out.
from collections import deque class Solution(object): def longestValidParentheses(self, s): """ :type s: str :rtype: int """ if len(s) == 0: return 0 st, max_run = deque(), 0 for idx, x in enumerate(s): if x == ")" and len(st) > 0 and s[st[-1]] == "(": st.pop() else: st.append(idx) st.appendleft(-1) st.append(len(s)) for i in range(1, len(st)): max_run = max(max_run, st[i]-st[i-1]-1) return max_run
Dynamic Programming Time & Space O(N)
- DP is an array of size N.
- dp[i] indicates the longest valid parentheses ending at index i.
- Note if s[i] = "(", then dp[i] is always 0. dp[i] is positive only when s[i] = ")".
- Now when s[i] = ")", we have a recursive formulation based on what we have at s[i-1].
- Interesting corner case: "()(())" which gives another condition when s[i]=")"
class Solution(object): def longestValidParentheses(self, s): """ :type s: str :rtype: int """ dp = *len(s) max_so_far = 0 for idx, ch in enumerate(s): if ch == ")": if idx >= 1 and s[idx-1] == "(": dp[idx] = dp[idx] + 2 dp[idx] = dp[idx] + dp[idx-2] if idx-2 >= 0 else dp[idx] elif idx >= 1 and s[idx-1] == ")": prev_index = idx-1 - dp[idx-1] if prev_index >= 0 and s[prev_index] == "(": dp[idx] = dp[idx-1] + 2 # For the case: "()(())" dp[idx] = dp[idx] + dp[prev_index-1] if prev_index >= 1 else dp[idx] max_so_far = max(max_so_far, dp[idx]) return max_so_far
Solution with No Extra Space