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

Stack

Two Counters

## 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/