# Longest valid Parentheses

Given a string A containing just the characters ’(‘ and ’)’.

Find the length of the longest valid (well-formed) parentheses substring.

Input Format:

```The only argument given is string A.
```
Output Format:

```Return the length of the longest valid (well-formed) parentheses substring.
```
Constraints:

```1 <= length(A) <= 750000
```
For Example

```Input 1:
A = "(()"
Output 1:
2
Explanation 1:
The longest valid parentheses substring is "()", which has length = 2.

Input 2:
A = ")()())"
Output 2:
4
Explanation 2:
The longest valid parentheses substring is "()()", which has length = 4.```
Solution:

Time: O(n)
Space: O(n)

```public class Solution {
public int longestValidParentheses(String A) {
// top of stack is the index of the end of previous parenthese
Deque<Integer> stack = new ArrayDeque<>();
int maxSize = 0;
int i = 0;
stack.push(-1);
while (i < A.length()) {
char c = A.charAt(i);
if (c == '(') {
stack.push(i);
} else {
stack.pop();
if (stack.isEmpty()) {
stack.push(i);
} else {
maxSize = Math.max(maxSize, i - stack.peekFirst());
}
}
i ++;
}
return maxSize;
}
}```