Find the length of the longest valid parenthesis sequence in a string, in O(n) time

I did this question before, and it is not easy to come up with O(n) solution under pressure. Here is it, which is solved with stack.

   private int getLongestLenByStack(String s) {
    //use last to store the last matched index
    int len = s.length(), maxLen = 0, last = -1;
    if (len == 0 || len == 1)
        return 0;

    //use this stack to store the index of '('
    Stack<Integer> stack = new Stack<Integer>();
    for (int i = 0; i < len; i++) {
        if (s.charAt(i) == '(') 
            stack.push(i);
        else {
            //if stack is empty, it means that we already found a complete valid combo
            //update the last index.
            if (stack.isEmpty()) {
                last = i;        
            } else {
                stack.pop();
                //found a complete valid combo and calculate max length
                if (stack.isEmpty()) 
                    maxLen = Math.max(maxLen, i - last);
                else
                //calculate current max length
                    maxLen = Math.max(maxLen, i - stack.peek());
            }
        }
    }

    return maxLen;
}

We need to store indexes of previously starting brackets in a stack.

We push the first element of stack as a special element as "-1" or any other number which will not occur in the indexes.

Now we traverse through the string, when we encounter "(" braces we push them, else when we encounter ")" we first pop them and

If stack is not empty, we find length of maximum valid substring till that point by taking maximum of result(initialised as zero) and the difference between current index and index at top of the stack.

Else if stack is empty we push the index.

int result=0;
stack<int> s1;
s1.push(-1);
for(int i=0;i<s.size();++i)
{
    if(s[i]=='(')
        s1.push(i);

    else if(s[i]==')')
    {
        s1.pop();

        if(!s1.empty())
            result=max(result,i-s1.top());
        else
            s1.push(i);
    }
}
cout<<result<<endl;

Here 's' is the string and 's1' is the stack.

You can increment/decrement an int variable for each open-parenthesis/close-parenthesis respectively. Keep track of the number of such valid operations (where the variable doesn't go below 0) as the current length, and keep track of the longest-such as the max.

public int getLongestLen(String s) {
    if (s == null || s.length() == 0) {
        return 0;       
    }

    int stack = 0;
    int counter = 0;
    int max = 0;

    for (Character c: s.toCharArray()) {
        if (c == '(') {
            stack++;
        }
        if (c == ')') {
            stack--;
        }
        if (stack >= 0) {
            counter++;
        }
        if (stack < 0) {
            counter = 0;
            stack = 0;
        }
        if (counter > max && stack == 0) {
            max = counter;
        }
    }

    return max;
}