# 0032. Longest Valid Parentheses

<https://leetcode.com/problems/longest-valid-parentheses>

## Description

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

**Example 1:**

```
**Input:** s = "(()"
**Output:** 2
**Explanation:** The longest valid parentheses substring is "()".
```

**Example 2:**

```
**Input:** s = ")()())"
**Output:** 4
**Explanation:** The longest valid parentheses substring is "()()".
```

**Example 3:**

```
**Input:** s = ""
**Output:** 0
```

**Constraints:**

* `0 <= s.length <= 3 * 104`
* `s[i]` is `'('`, or `')'`.

## ac1: stack

parentheses -> stack

```java
class Solution {
    public int longestValidParentheses(String s) {
        // edge case
        if (s == null | s.length() < 2) return 0;

        // iterate
        Stack<Integer> stack = new Stack<Integer>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == ')' && !stack.isEmpty() && s.charAt(stack.peek()) == '(') {
                stack.pop();
            } else {
                stack.push(i);
            }
        }
        stack.push(s.length());

        // check remaining indices
        int max = 0, curr = stack.pop();
        while (!stack.isEmpty()) {
            int next = stack.pop();
            max = Math.max(max, curr - next - 1);
            curr = next;
        }
        max = Math.max(max, curr - 0); // check last one

        // result
        return max;
    }
}

/*
parentheses -> stack
iterate, if '(' push to stack, if ')' check:
    if stack.peek() == '(', stack.pop(), kill one pair parentheses
    else push
stack record indices
finally check remaining indices, record longest one
*/
```

## ac2: 2 pointers

```java
class Solution {
    public int longestValidParentheses(String s) {
        // edge case
        if (s == null | s.length() < 2) return 0;

        int max = 0;

        // iterate, keep track of left bracket & right bracket
        int l = 0, r = 0;
            // 1st, left -> right
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') l++;
            else r++;
            if (l == r) {
                max = Math.max(max, l * 2);
            }
            else if (l < r) {
                l = 0;
                r = 0;
            }
        }
            // 2nd, right -> left
        l = 0; r = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            char c = s.charAt(i);
            if (c == '(') l++;
            else r++;
            if (l == r) {
                max = Math.max(max, l * 2);
            }
            else if (l > r) {
                l = 0;
                r = 0;
            }
        }

        // result
        return max;
    }
}

/*
2 pointers
keep track of left bracket & right bracket: meet ( left++, meet ) right++
when left = right, means valid parentheses, track length
if left < right, invalid, pass, set 0 to restart

2 pass, left -> right, then right -> left. because 1 pass cannot track those when left > right

*/
```

## ac3: DP

```java
class Solution {
    public int longestValidParentheses(String s) {
        // edge case
        if (s == null | s.length() < 2) return 0;

        int max = 0;

        // dp
        int[] dp = new int[s.length()];
        for (int i = 1; i < dp.length; i++) {
            char c = s.charAt(i);
            if (c == ')') {
                int prev = i - dp[i-1] - 1;  // careful boundary
                if (prev >= 0 && s.charAt(prev) == '(') {
                    dp[i] = 2 + dp[i-1] + (prev > 0 ? dp[prev-1] : 0);
                    max = Math.max(max, dp[i]);
                }
            }
        }

        // result
        return max;
    }
}

/*
DP
state: dp[i], the length of valid parentheses end with current index
function: 
    meet (, dp[i] = 0, do nothing
    meet ),
        if s.charAt(i-1) == '(', dp[i] = dp[i-1] + 2
        if i - dp[i-1] - 1 is '(', dp[i] = 2 + dp[i-1] + dp[i - dp[i-1] - 2]


*/
```


---

# 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://jaywin.gitbook.io/leetcode/solutions/0032-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.