Longest valid Parenthesis - Approach 2
Intution \n The basic fact we know is that for a string to have valid parenthesis, is that number of opening brackets should be equal to number of closing brack
# Intution \n The basic fact we know is that for a string to have valid parenthesis, is that number of opening brackets should be equal to number of closing brackets . \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\nHere is the second approach to this problem that does not uses a stack .\nIn this approach , we maintain three counters :\n1. open \n2. close\n3. max\n       \nNow , whenever we encounter any opening parenthesis , we increment the **open counter** \nand whenever we encounter any closing bracket , we increment the **close counter**.\n\nIf the value of open and close counters are same , then we know that it is a valid substring and we then calculate it\'s length by formula :\n**open+close**\n\nNow , here is the plot twist . we have to parse the string twice -\n- Once, from starting to end \n- end to start\n                  why?\nbecause it may happen that a substring that may look invalid from  start to end , it can be  valid if traversed from end to start.\n\nHence while traversing from start to end , we have to put a condition that if **close > open** , then it will be an invalid substring  obviously!\n\nand while traversing from end to start , we will put up the condition that if **open > close** then , the substring will be an invalid one .\n\n# Complexity\n- Time complexity : $$O(n)$$\n<!-- Add your time complexity here, e.g.  -->\n\n- Space complexity : $$O(1)$$ \n<!-- Add your space complexity here, e.g. -->\n\n# Code\n```\nclass Solution {\n    public int longestValidParentheses(String s) {\n        int open = 0 , close = 0;\n        int max = 0;\n        \n        // 0 -- n\n        for(int i=0;i<s.length();i++){\n            char c = s.charAt(i);\n            if(c == \'(\'){\n                open++;\n            }\n            else{\n                close++;\n            }\n            \n            if(open == close){\n                int len = open + close;\n                max = Math.max(max,len);\n            }\n            else if(close > open ){\n                open = close = 0;\n            }\n        }\n        \n        open = close = 0;\n        // n -- 0\n        for(int i= s.length()-1; i>=0 ;i--){\n            char c = s.charAt(i);\n            if(c == \'(\'){\n                open++;\n            }\n            else{\n                close++;\n            }\n            \n            if(open == close){\n                int len = open + close;\n                max = Math.max(max,len);\n            }\n            else if(open > close ){\n                open = close = 0;\n            }\n        }\n        \n        return max;\n    }\n}\n```
['String', 'Dynamic Programming', 'Stack', 'Java']