leetcode Question 46: Longest Valid Parentheses

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.

Analysis:
Key point is to save the previous result, e.g. ()(), when the second ( is scanned, the result length should add the first pair of ().

Some special cases should be considered:
()()  max = 4
(()() max = 4
()(() max = 2

We want the complexity to be O(n). Thus iteration is from the first element to the last of the string.

Stack is used to stored the character.

If current character is '(', push into the stack.
If current character is ')',
    Case 1:  the stack is empty, reset previous result to zero. Here we renew a pointer to store the earliest index.
    Case 2: the stack is not empty, pop the top element. if the top element is '(' , (which means a () pair is found), then if the poped stack is empty, (which means the previous pairs should be added.), len = current pos - previous pos +1; If the poped stack is not empty, len = current pos- index of stack top element.




Source Code:

class Solution {
public:
    int longestValidParentheses(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (s.size()<2) {return 0;}
        stack<pair<char,int> > st;
        int maxl=0;
        int i=0;
        int t=0;
        while (i<s.size()){            
            if (s[i]=='(') {st.push(make_pair(s[i],i));}
            else{
                if (st.empty()){t=i+1;}
                if (!st.empty()){
                    pair<char,int> tmp = st.top();
                    st.pop();
                    if (tmp.first=='('){
                        if (!st.empty()){maxl=max(maxl,(i-st.top().second));} //key step, i-st.top().second, but not the tmp.second.
                        else{maxl=max(maxl,i-t+1);}
                    }
                }        
            }
            i++;
        }
        return maxl;
    }
};