# 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

```java
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

```java
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/>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/stack/longest-valid-parentheses.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.