Interesting solution to the problem of finding the Longest Valid Parentheses substring

gistfile1.txt

public class Solution {
    public int longestValidParentheses(String s) {
        int maxLen = 0;
        // the index that right before the beginning of the current longest substring 
        int left = -1;
        
        Stack<Integer> stack = new Stack<Integer>();
        for (int i=0; i<s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                if (stack.isEmpty()) {
                    // more ')' than '(', consider a new substring
                    left = i;
                } else {
                    stack.pop();
                    if (stack.isEmpty()) {
                        // stack is empty, consider adding the pair to the current substring
                        maxLen = Math.max(maxLen, i - left);
                    } else {
                        // stack is not empty, more '(' than ')'
                        // get the difference between the current pos and the first '(' on stack
                        maxLen = Math.max(maxLen, i - stack.peek());
                    }
                }
            }
        }
        return maxLen;
    }
}