# 32. Longest Valid Parentheses (Hard)

https://leetcode.com/problems/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 `"()()"`
```

## Solutions

``````class Solution {
public int longestValidParentheses(String s) {
Stack<Integer> stack = new Stack<>();

// Keep the track of ith char whether s.char[i] is part of a valid parenthese pair or not.
boolean[] track = new boolean[s.length()];
Arrays.fill(track, false);

// sort out all the valid parenthese pairs
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push(i);
}

// if s.charAt(index) matches s.char(i) and for a valid pair, set both track[i]
// and track[index] true
if (s.charAt(i) == ')' && !stack.isEmpty()) {
int j = stack.pop();
track[i] = true;
track[j] = true;
}
}

int max = 0;

// sort out the consecutive elements that are able to form valid parentheses pairs
int count = 0;
for (int i = 0; i < track.length; i++) {
if (track[i]) {
count++;
} else {
max = Math.max(max, count);
count = 0;
}
}

return Math.max(max, count);
}
}
``````

## Incorrect Solutions

``````class Solution {

// TODO Incorrect solution

// "()(()" expected 2, output 4

// The key idea of solving this problem is using stack

public int longestValidParentheses(String s) {
if (s == null || s.length() <= 1) {
return 0;
}

Stack<Character> stack = new Stack<>();

int max = 0;
int count = 0;

int len = s.length();
for (int i = 0; i < len; i++) {
// if it is open parenthese, push into stack
if (s.charAt(i) == '(') {
stack.push('(');
continue;
}

// if the ith char is ')' and stack is not empty, we can form a valid pair of parenthese
if (s.charAt(i) == ')' && !stack.isEmpty()) {
stack.pop();
count += 2;

max = Math.max(count, max);
}
// mal-formed
else if (s.charAt(i) == ')' && stack.isEmpty()) {
count = 0;
stack.clear();
}
}

return max;
}
}
``````