[LeetCode] Longest Valid Parentheses

Problem Statement (link):

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:
Stack should be the first thought when we are asked about parentheses validation problem, as we could push the '(' and match it with any ')' we meet in the future.

However, the stack algorithm for this problem is not straight-forward. The reason is simple, as the problem allows any kind of parentheses combination; while the conventional stack algorithm requires consecutive validness.

Let's not abandon the conventional stack idea, i.e., push when meet '(', pop when meet ')'. Additionally, suppose we use a start variable to record the index of the latest possible start of a valid sequence:
- First, after a sequential push() operation, if the stack is empty, it implies so far we only see ')'. Thus we need to keep updating start variable to indicate the start of possible valid sequence shouldn't include any previous ')'s;
- Next, if we meet some ')' and pop() them out, we want to keep updating maxLen. However, there are two situations:
1) the stack is empty after we pop() something. For instance, s = " ( ) ", after we pop() the ')', the stack should be empty and we need to update the maxLen. If we have start indicating the possible start of a valid sequence, start = -1 (which is also the initial value), current valid length = i - start. And we update maxLen by taking the max between current valid length and previous possible maxLen.
2) the stack is not empty after we pop() something. For instance, s = ' ( ( ) ', after we pop the ')', the stack is not empty, and we also need to update the maxLen. Now, current valid length = 2, which is actually i - index of the first '(', the index of the first '(' could be obtained from peeking the top of the stack - as the stack is not empty right now, i.e., current valid length = i - stack.top(). Now, we get the idea that all the indices that are still in stack indicate the indices of the "invalid/unused" '('.

It's a bit difficult to get the idea of recording the valid length, working through an example would help.

Furthermore, the time complexity and worst space complexity is O(n), where n is length of the string.

Code:

class Solution {
public:
    int longestValidParentheses(string s) {
        int maxLen=0;
        int start=-1;    // the possible start of a valid seq
        stack<int> st;  // save the index of '('
        for (int i=0; i<s.length(); i++) {
            if (s[i]=='(') {
                st.push(i);
            }
            else {
                if (st.empty()) {
                    start=i;
                }
                else {
                    st.pop();
                    if (st.empty()) {
                        maxLen=max(maxLen, i-start);
                    }
                    else {
                        maxLen=max(maxLen, i-st.top());
                    }
                }
            }
        }
        return maxLen;
    }
};