LeetCode Longest Valid Parentheses

Description

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.

The original problem is here.

The original code is here.

My Solution

I solve this problem in C++, as below:

/*
*Longest Valid Parentheses 
*Author: shuaijiang
*Email: zhaoshuaijiang8@gmail.com
*/
#include<iostream>
#include<stack>
#include<stdlib.h>
using namespace std;

class Solution {
public:
    int longestValidParentheses(string s) {
        int len = s.size();
        if( len <= 0)
            return 0;
        stack<int> myStack; // save the index of '('
        int maxLen = 0, last = -1;
        for(int i=0; i<len; i++){
            if(s[i] == '(')
                myStack.push(i);
            else{
                if(!myStack.empty()){
                    myStack.pop();
                    if(myStack.empty())
                        maxLen = max(maxLen, i-last);
                    else
                        maxLen = max(maxLen, i-myStack.top());
                }
                else{
                    last = i;
                }
            }
        }
        return maxLen;
    }
};

Note

To solve the problem, a stack is used to save the index of ‘(‘. If the current char is ‘)’, pop the stack if it is not empty; otherwise, let last = the current index. After pop the stack, if the stack is empty, then get the length of new group valid parentheses by i-last; else, the length is i-stack.top().