> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/stacks-and-queues/longest-valid-parentheses.md).

# 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 "()()"
```

```java
class Solution {
    public int longestValidParentheses(String s) {
        Deque<Integer> st = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            if (st.size() == 0)
                st.push(i);
            else if (s.charAt(st.peek()) == '(' && s.charAt(i) == ')')
                st.pop();
            else
                st.push(i);
        }
        if (st.size() == 0)
            return s.length();
        int end = s.length();
        int ans = 0;
        while (st.size() != 0) {
            ans = Math.max(ans, end - st.peek() - 1);
            end = st.pop();
        }
        ans = Math.max(ans, end - 0);
        return ans;
    }
}
```