LeetCode: Longest Valid Parentheses

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

---

Just like parentheses matching, we can use a stack to keep the starting index of each valid substring.

C++ Code:

/*
 * func: longest_valid_parentheses
 * goal: find the length of the longest valid parentheses substring
 * @param s: input string s
 * return: the maximum length
 */
int longest_valid_parentheses(string s){
    int max_length = 0;
    int last = -1;
    vector<int> helper;
    for(int i=0; i<static_cast<int>(s.length()); ++i){
        if(s.at(i) == '('){
            helper.emplace_back(i);
        }else{
            if(helper.empty()){
                last = i;
            }else{
                helper.pop_back();
                if(helper.empty()){
                    max_length = max(max_length, i - last);
                }else{
                    max_length = max(max_length, i - helper.back());
                }
            }
                
        }
    }
    return max_length;
}

Python Code:

# func: find the length of the longest valid
#       (well-formed) parentheses substring
# @param s: input parentheses string
# @return: the maximum length
# complexity: time O(n), space O(1)
def longest_valid_parentheses(s):
    #start index of each valid substring
    left = -1

    index = 0
    max_len = 0

    #list for indices of open parentheses
    open_stack = []

    while index < len(s):
        #If it is open parenthesis, add it to the stack
        if s[index] == '(':
            open_stack.append(index)
        else:
            #If we are starting with close parenthesis, we
            #need to change left index of the valid substring
            if not open_stack:
                left = index
            else:
                open_stack = open_stack[:-1]
                if not open_stack:
                    #If the stack is empty, the length will be index - left
                    max_len = max(max_len, index - left)
                else:
                    max_len = max(max_len, index - open_stack[-1])
        index += 1

    return max_len