# Simple JAVA solution, O(n) time, one stack

• ``````public class Solution {
public int longestValidParentheses(String s) {
Stack<Integer> stack = new Stack<Integer>();
int max=0;
int left = -1;
for(int j=0;j<s.length();j++){
if(s.charAt(j)=='(') stack.push(j);
else {
if (stack.isEmpty()) left=j;
else{
stack.pop();
if(stack.isEmpty()) max=Math.max(max,j-left);
else max=Math.max(max,j-stack.peek());
}
}
}
return max;
}
}
``````

• truly brilliant to store the index into stack (instead of the parentheses)

• Nice solution! Inspired by your solution. I changed a little to make it shorter and easier.

``````public class Solution {
public int longestValidParentheses(String s) {
int result = 0;
stack.push(-1);
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == ')' && stack.size() > 1 && s.charAt(stack.peek()) == '(') {
stack.pop();
result = Math.max(result, i - stack.peek());
} else {
stack.push(i);
}
}
return result;
}
}
``````

The idea is simple, we only update the result (max) when we find a "pair".
If we find a pair. We throw this pair away and see how big the gap is between current and previous invalid.
EX: "( )( )"
stack: -1, 0,
when we get to index 1 ")", the peek is "(" so we pop it out and see what's before "(".
In this example it's -1. So the gap is "current_index" - (-1) = 2.
The idea only update the result (max) when we find a "pair" and push -1 to stack first covered all edge cases.

• when I use the Stack instead of LinkedList, I got TLE, can anyone help me figure out why LinkedList used as a stack is faster than Stack presentation.

• The cleanest code for this problem. Thanks. But why do I get a RTE if I replace `stack.size() > 1` to `!stack.empty()` ??

• @EdickCoding Thank you for your code. I tried removing pushing -1 at first and I got TLE error, any idea? My code is:

``````public class Solution {
public static int longestValidParentheses(String s) {
Stack<Integer> stack = new Stack<>();
int result = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == ')' && stack.size() > 0 && s.charAt(stack.peek()) == '(') {
stack.pop();
result = Math.max(result, stack.size() == 0 ? i + 1 : i - stack.peek());
} else {
stack.push(i);
}
}
return result;
}
}

``````

Thank you!

• @quincyhehe I believe it will miss the corner case in that way.

• @kesai Thank you for your reply. But why does it fail the test case "(((((((((((((((((((" ? I've tried running locally and it was fine. Thanks.

• @quincyhehe I met the same problem, the system should has updated the test cases, and the DP method maybe help

• @liujunhongznn

Thank you! So you mean right now it can pass the OJ now?

• This post is deleted!

• @EdickCoding Amazing! Very clear explanation! You saved me!
I didn't notice that it ends up with TLE.
Deque is much faster than Stack, since it's un-synchronized (Stack extends Vector). Now it works!

• Actually i dont think your code is O(n)time. you ignore the time cost on stack calculate

• This post is deleted!

• nice solution
this is mine:

``````public class Solution {
public int longestValidParentheses(String s) {
if(s.length() == 0) return 0;
// int[] dp = new int[s.length()];
String reverse = new StringBuilder(s).reverse().toString();
return Math.max(helper(s, new char[]{'(',')'}), helper(reverse, new char[]{')','('}));
}

private int helper(String s, char[] param) {
int ret = 0;
int count = 0;
int len = 0;
for(int j = 0; j < s.length(); j++) {
if(s.charAt(j) ==param[0]) {
count++;
}else {
count--;
}
len++;
if(count == 0) {
ret = Math.max(ret, len);
}
if(count == -1) {
count = 0;
len = 0;
}
}
return ret;
}
}
``````

• Just awesome.

• s.charAt(stack.peek()) == '('

You have only numbers in the stack and not parenthesis

• Is this solution actually DP? Using stack this solution just calculates the length of valid sequences and return the max length. I don't understand the DP subproblem in this solution.

• @gogoflg2016 @quincyhehe Try using ArrayDeque instead of Stack and specify the initial capacity like this:
Deque<Integer> stack = new ArrayDeque<>(s.length());

Stack and ArrayDeque are implemented with resizable array, and every time it is full, all of the elements will be copied to a new allocated array, which is costly if this process is invoked repeatedly and thus leads to TLE on large test cases. Specifying an initial capacity can prevent this from happening.

• Javascript version:

``````var longestValidParentheses = function(s) {
var stk = []
var mx = 0
var left = -1
for(var j = 0; j < s.length; j++) {
if(s[j] == '(') stk.push(j)
else {
if (stk.length == 0) left = j
else {
stk.pop()
if(stk.length == 0) mx = Math.max(mx, j - left)
else mx = Math.max(mx, j - stk[stk.length - 1])
}
}
}
return mx;
};
``````

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