32. Longest Valid Parentheses - cocoder39/coco39_LC GitHub Wiki

32. Longest Valid Parentheses

Notes 2022

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        stack = []
        for i, ch in enumerate(s):
            if ch == ')' and stack and s[stack[-1]] == '(':
                stack.pop()
            else:
                stack.append(i)
        
        res = 0
        end = len(s)
        while stack:
            begin = stack.pop()
            res = max(res, end-begin-1)
            end = begin
        res = max(res, end) # left most boundary end = end - (-1) - 1
        return res

========================================================================

solution 1: use a stack. store index of parentheses that can not be pair, the length of valid parentheses is the length between two parentheses in stack.

  • scan the string,

if visit a '(', push it into stack

if visit a ')', check if it can pair with top of stack (check if top is '(') if so, pop out top else, push the ')' into stack

  • scan stack, get the length of each valid parentheses.
int longestValidParentheses(string s) {
        stack<int> mystack;
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == ')' && ! mystack.empty() && s[mystack.top()] == '(') {
                mystack.pop();
            }
            else {
                mystack.push(i);
            }
        }
        
        int res = 0;
        int end = s.length();
        while (! mystack.empty()) {
            int start = mystack.top();
            mystack.pop();
            res = max(res, end - start - 1);
            end = start;
        }
        res = max(res, end);
        return res;
    }

solution 2:

dp[i] is the length of valid parentheses ending with s[i - 1].

  • if s[i - 1] == '(', dp[i] = 0 since no valid parentheses can end with '('
  • if s[i - 1] == ')', we have the opportunity to extend the length of valid parentheses. To extend the length, we need find out the closest invalid parentheses, whose index should be i - 2 - dp[i - 1]

if s[i - 2] == '(', the closest invalid parentheses is this '('. dp[i] = dp[i - 2] + 2. In other words, if s[i - 3] is a valid ending, s[i - 2] and s[i - 1] would extend the valid parentheses. if s[i - 3] is not a valid ending, dp[i] = 2 because of s[i - 2] and s[i - 1].

if s[i - 2] == ')', no matter s[i - 2] is a valid ending (dp[i - 1] > 0) or invalid (dp[i - 1] = 0), left_pair = (i - 1) - 1 - dp[i - 1] is the index of the invalid parentheses. If the char is '(', then it can pair with s[i - 1], extending the length. else if the char is '(', it cannot pair with s[i - 1], and have no relationship with s[left_pair + 1 .. i - 2], so it cannot extend the length.

int longestValidParentheses(string s) {
        //dp[i] is longest valid parentheses ending with s[i - 1]
        //dp[i] = 0 if s[i - 1] = '('
        //only update dp for s[i - 1] = ')'
        vector<int> dp(s.length() + 1); 
        int res = 0;
        
        for (int i = 1; i <= s.length(); i++) {
            if (s[i - 1] == ')') {
                //if s[i - 2] = '(', left_pair = i - 1 since dp[i - 2] = 0
                //if s[i - 2] = ')' && s[i - 1] is not a valid ending, left_pair = i - 2, s[left_pair] = ')', no updation
                int left_pair = i - 2 - dp[i - 1];
                if (left_pair >= 0 && s[left_pair] == '(') {
                    dp[i] = 2 + dp[i - 1] + dp[left_pair];
                    res = max(res, dp[i]);
                }
            }
        }
        return res;
    }
⚠️ **GitHub.com Fallback** ⚠️