Leetcode: Max valid parenthesis

maxValidParenthesis.cpp

/*
 * I found this one tough. I figured out a solution that used O(n) space almost immediately, but this
 * solution is much more elegant. The problem states counting the max size of the valid parenthesis.
 * For example, (()() would be four. The data structure to use here is a stack, but there is a trick.
 * The trick is to note that if the stack is empty, and a right bracket comes along ')', then the
 * size calculation must start from 0 again. This is because that is invalid and will never
 * produce a valid parenthesis pair. So we initialise a variable called lastRight, which is set at -1
 * When the stack is empty, this is the variable that will be used to calculate the size. When a ')'
 * comes along, then this variable is updated. When the stack is not empty, then we just substract the
 * the current increment value from whatever is on the top of the stack.
 */

class Solution {
public:
    int longestValidParentheses(string s) {
        int lastRight = -1,
            maxValidCount = 0;
        
        stack<int> st;
        
        for (int i=0; i < s.size(); i++) {
            if (!st.empty() && s[st.top()] == '(' && s[i] ==')') {
                st.pop();
                if (st.empty()) {
                    maxValidCount = max(maxValidCount, i-lastRight);
                } else {
                    maxValidCount = max(maxValidCount, i-st.top());
                }
            } else {
                if (s[i] == ')') {
                    lastRight = i;
                } else {
                    st.push(i);
                }
            }
        }
        
        return maxValidCount;
    }
};

maxValidParenthesis_2.cpp

/*
 * I did this over again, and yes, I found it tought again. New solution this time
 * The idea is to measure the length of the valid parenthesis. It is done by
 * substracting the current index from a start position that is on the stack
 * The start position is calculated as follows: If set to -1, then set start
 * to the current index, otherwise use its contents as the start position. Start
 * will always be -1, but when two brackets match, then start will be set to 
 * the index of the bracket that was on the stack
 */
 
class Solution {
public:
    int longestValidParentheses(string s) {
        int maxValid = 0,
            start = -1;
        stack<int> st;
        
        for (int i=0; i < s.size(); i++) {
            if (st.empty() && s[i] == ')') {
                start = -1;
                continue;
            }
            
            if (s[i] == '(') {
                st.push((start == -1) ? i : start);
                start = -1;
            } else {
                maxValid = max(maxValid, i-st.top()+1);
                start = st.top();
                st.pop();
            }
        }
        
        return maxValid;
    }
};