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,jleft);
else max=Math.max(max,jstack.peek());
}
}
}
return max;
}
}
Simple JAVA solution, O(n) time, one stack


Nice solution! Inspired by your solution. I changed a little to make it shorter and easier.
public class Solution { public int longestValidParentheses(String s) { LinkedList<Integer> stack = new LinkedList<>(); 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.

@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!


@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


@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 unsynchronized (Stack extends Vector). Now it works!

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; } }

@EdickCoding said in Simple JAVA solution, O(n) time, one stack:
s.charAt(stack.peek()) == '('
You have only numbers in the stack and not parenthesis

@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; };