Longest Valid Parentheses

Given a string containing just the characters'('and')', find the length of the longest valid (well-formed) parentheses substring.

Example 1:

Input:
 "(()"

Output:
 2

Explanation:
 The longest valid parentheses substring is 
"()"

Example 2:

Input:
 "
)()())
"

Output:
 4

Explanation:
 The longest valid parentheses substring is 
"()()"

Analysis

跟Valid Parentheses有些关联，不过如果用Valid Parentheses中的function，那么生成所有substring需要O(n^2)，逐个验证则需要O(n)，因为是嵌套循环，所以时间复杂度O(n^3)。看起来算法并不够有效率，基本等同Brute Force。

Stack

如果直接寻找问题的解法，那么可以推广stack的方法，不过在stack中改为存取元素下标。

Two Counters

这一题最喜欢的方法其实是利用two counters，left, right 分别记录当前符合顺序的 ( 和 )的个数，从左往右扫描时，如果right > left 则将两个counter都清零，反之如果从右往左扫描时 left > right 则清零两个counter。

Solution

class Solution {
    public int longestValidParentheses(String s) {
        Stack<Integer> stack = new Stack<Integer>();
        int len = s.length();
        int longest = 0;
        stack.push(-1);
        for (int i = 0; i < len; i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    longest = Math.max(longest, i - stack.peek());
                }
            }
        }
        return longest;
    }
}

Two Counters Approach - O(n) time, O(1) space

public class Solution {
    public int longestValidParentheses(String s) {
        int left = 0, right = 0, maxlength = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                maxlength = Math.max(maxlength, 2 * right);
            } else if (right >= left) {
                left = right = 0;
            }
        }
        left = right = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                maxlength = Math.max(maxlength, 2 * left);
            } else if (left >= right) {
                left = right = 0;
            }
        }
        return maxlength;
    }
}

Reference

https://leetcode.com/problems/longest-valid-parentheses/solution/