# Direct solution with one stack

• ``````/*
use a stack to store parentheses and length of already matched pairs.
e.g.,
input: ) ( ( ) ) ( )
0 1 2 3 4 5 6
We scan )(( and store in stack, after scanned ')' in 3rd position, we find it match with
'(' in 2rd position so pop '(' and push number 2(length of matched pair) to stack. The
current stack is [), (, 2].

Then scan 4th position , it matches 1st position, because we have a matched pair between
them, pop twice, and push (2+2=4), we call this indirect match. The current stack is
[), 4], then scan 5th position, nothing happens. The current stack is [), 4, (].

Then we find a direct match ('(' follows ')' directly) and the previous item in stack is
a number 4,  we have to merge consecutive numbers, and the final stack will be [), 6].

Finally, we pop all the items in stack and find the largest number, that's the max length.

As you see, all the tricks happen in indirect match and merge consecutive numbers, and
recursion happens at most twice for one call, because we will merge every consecutive
numbers as long as them exist, so the time-complexity is O(N).
Actually, we can use just Array because the biggest capacity of stack is s.length();
*/
public class LongestValidParentheses {
public static int longestValidParentheses(String s) {
Stack<Integer> stack = new Stack<Integer>();
// use negative value to store '(' and ')', we will use
// positive value to store length of valid parentheses
for (int i = 0; i < s.length(); i++)
int maxLen = 0;
while (!stack.empty()) {
int a = stack.pop();
if (a > maxLen) maxLen = a;
}
return maxLen;
}

private static void add(Stack<Integer> stack, int now) {
if (stack.empty()) {
stack.push(now);
} else if (isParenthese(now)) {
int last = stack.peek();
if (isParenthese(last)) { // [stack, parenthese, parenthese]
if (match(last, now)) { // just match
stack.pop();
add(stack, 2); // use recursion to merge possible consecutive numbers
} else {
stack.push(now);
}
} else { // [stack, number, parenthese]
stack.pop();
if (stack.empty()) { // [number, parenthese]
stack.push(last);
stack.push(now);
} else {
int llast = stack.peek();
if (isParenthese(llast)) { // [stack, parenthese, number, parenthese]
if (match(llast, now)) { // match and merge
stack.pop();
add(stack, 2 + last); // possible merge of consecutive numbers
} else {
stack.push(last);
stack.push(now);
}
} else { // [stack, number, number, parenthese]
// Not possible. All the consecutive numbers will be
// merged before this case happens
}
}
}
} else { // now is a number
int last = stack.peek();
if (!isParenthese(last)) { // [stack, number, number], merge
stack.pop();
// no need to use recursion because previous
// consecutive numbers are already merged
stack.push(last + now);
} else { // [stack, parenthese, number]
stack.push(now);
}
}
}

private static boolean isParenthese(int ch) {
return -ch == '(' || -ch == ')';
}

private static boolean match(int a, int b) {
return -a == '(' && -b == ')';
}
``````

}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.