Very Easy To Understand - 5 ms - O(n) solution without Stack or DP
for input example:\n\n"()()))((()(())(()))((())(()()()()()()(((((())))))())()())()(())(())())))))(())()((((((((()()(())))))())())))()(((()())()))(((()()((((("\n
for input example:\n\n"()()))((()(())(()))((())(()()()()()()(((((())))))())()())()(())(())())))))(())()((((((((()()(())))))())())))()(((()())()))(((()()((((("\n\nI scan the string forward and backward change the string to:\n\n()()##((()(())(()))((())(()()()()()()(((((())))))())()())()(())(())())####(())()((((((((()()(())))))())())))()(((()())()))###()()#####\n\nthe invalid ( or ) are removed.\n\nThen you count the longest valid substring length.\n\n\n    public class Solution {\n        public int longestValidParentheses(String s) {\n            char[] c = s.toCharArray();\n            int len = c.length, t = 0, ans = 0;\n            for (int i = 0, y = 0; i < len; i++)\n                if (c[i] == '(')\n                    y++;\n                else if (c[i] == ')' && --y < 0) {\n                    y = 0;\n                    c[i] = '#';\n                }\n                \n            for (int i = len - 1, y = 0; i >= 0; i--) {\n                if (c[i] == ')')\n                    y++;\n                else if (c[i] == '(' && --y < 0) {\n                    y = 0;\n                    c[i] = '#';\n                }\n                \n                t = (c[i] == '#') ? 0 : t + 1;\n                ans = Math.max(ans, t);\n            }\n            System.out.println(new String(c));\n            \n            return ans;\n        }\n    }
[]