Two Java solutions with explanation. Stack & DP. Short & easy to understand.
// Stack solution  10ms  \nThe idea is simple, we only update the result (max) when we find a "pair".  \nIf we find a pair. We throw this pair away and see how 
// **Stack solution  10ms**  \nThe idea is simple, we only update the result (max) when we find a "pair".  \nIf we find a pair. We throw this pair away and see how big the gap is between current and previous invalid.  \nEX: "( )( )"  \nstack: -1, 0,  \nwhen we get to index 1 ")", the peek is "(" so we pop it out and see what's before "(".  \nIn this example it's -1. So the gap is "current_index" - (-1) = 2.  \n\nThe idea **only update the result (max) when we find a "pair"** and **push -1 to stack first** covered all edge cases.  \n\n    public class Solution {\n        public int longestValidParentheses(String s) {\n            LinkedList<Integer> stack = new LinkedList<>();\n            int result = 0;\n            stack.push(-1);\n            for (int i = 0; i < s.length(); i++) {\n                if (s.charAt(i) == ')' && stack.size() > 1 && s.charAt(stack.peek()) == '(') {\n                    stack.pop();\n                    result = Math.max(result, i - stack.peek());\n                } else {\n                    stack.push(i);\n                }\n            }\n            return result;\n        }\n    }\n\n\n\n**//DP solution  4ms**  \nThe idea is go through the string and use DP to store the longest valid parentheses at that point.  \ntake example "()(())"  \ni :    [0,1,2,3,4,5]  \ns :   [( ,) ,( ,( ,) ,) ]  \nDP:[0,2,0,0,2,6]  \n\n1, We count all the \u2018(\u2018.  \n2, If we find a \u2018)\u2019 and \u2018(\u2018 counter is not 0, we have at least a valid result size of 2. \u201c()"  \n3, Check the the one before (i - 1). If DP[i - 1] is not 0 means we have something like this \u201c(())\u201d . This will have DP \u201c0024"  \n4, We might have something before "(())\u201d. Take "()(())\u201d example, Check the i = 1 because this might be a consecutive valid string.  \n\n    public class Solution {\n        public int longestValidParentheses(String s) {\n            int[] dp = new int[s.length()];\n            int result = 0;\n            int leftCount = 0;\n            for (int i = 0; i < s.length(); i++) {\n                if (s.charAt(i) == '(') {\n                    leftCount++;\n                } else if (leftCount > 0){\n                    dp[i] = dp[i - 1] + 2;\n                    dp[i] += (i - dp[i]) >= 0 ? dp[i - dp[i]] : 0;\n                    result = Math.max(result, dp[i]);\n                    leftCount--;\n                }\n            }\n            return result;\n        }\n    }
['Dynamic Programming', 'Stack', 'Java']