Longest Valid Parentheses

Problem

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

Example 1:

Input: “(()”
Output: 2
Explanation: The longest valid parentheses substring is “()”

Example 2:

Input: “)()())”
Output: 4
Explanation: The longest valid parentheses substring is “()()”

Requirements

  • string containing just the characters ‘(‘ and ‘)’
  • find the length of the longest valid (well-formed) parentheses substring
  • string can be empty? yes

Approach

We can use a stack to keep track of opening parentheses. When we see an opening parenthesis, we push index of opening parenthesis to stack. When we see closing, we pop off stack and add 2 to a running counter. After stack is empty we update the global max of counts.

1
2
3
4
5
6
7
class Solution {
public:
    int longestValidParentheses(string s) {
    int max_len = 0;
    int curr_len = 0;
    // TODO
};