Java stack solution , O(n)
public class Solution {\n    public int longestValidParentheses(String s) {\n        if(s == null || s.length() <= 1){\n            return 0;\n        }\n      
    public class Solution {\n    public int longestValidParentheses(String s) {\n        if(s == null || s.length() <= 1){\n            return 0;\n        }\n        int start = -1;\n        int res = 0;\n        LinkedList<Integer> stack = new LinkedList<Integer>();\n        for(int i=0;i<s.length();i++){\n            if(s.charAt(i) == '('){\n                stack.push(i);\n            }else{\n                if(!stack.isEmpty()){\n                    stack.pop();\n                    if(!stack.isEmpty()){\n                        res = Math.max(res,i-stack.peek());\n                    }else{\n                        res = Math.max(res,i-start);\n                    }\n                }else{\n                    start = i;\n                }\n            }\n        }\n        return res;\n    }\n}
[]