[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.

Pasted from <http://leetcode.com/onlinejudge>

Analysis:

Using a stack to push and pop the valid parentheses and the left in the stack is the invalid parentheses. These invalid parentheses are the separator of all groups of valid parentheses.  If we know the index of the invalid parenthesis, then the gap  between indexes are the length of the valid parentheses.

Example: ()(()()()

Invalid parentheses index : 2. So the valid parentheses are 0 to 2 and 2 to 9, which is 6.

int longestValidParentheses(string s) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    int n = s.size();
    int maxLength = 0;
    stack idxStack;
    for (int i=0; i 0)
                idxStack.pop();
            else
                idxStack.push(-1*(i+1)); //use negative to indicate it is  ")"
        }
    }
   
    int e = n + 1;  //the last invalid index is n+1
    while(!idxStack.empty())
    {
        int idx = abs(idxStack.top());
        maxLength = max(maxLength, e - idx -1);
        e = idx;
        idxStack.pop();
    }
   
    maxLength = max(maxLength, e - 1); //the first invalid index is 0 (index in stack begin from 1)

    return maxLength;

}