Longest Valid Parenthesis Approach 1.
\n# Approach\n Describe your approach to solving the problem. \n\nThis problem can be solved using two approaches -\n1. using Stack \n2. without using stack \n\
\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\nThis problem can be solved using two approaches -\n1. using Stack \n2. without using stack \n\n\n---\n\n# Using Stack \n In this approach , we use a stack to push and pop the indices of the parenthesis in the string . The stack is initialized with -1.\nWhen we encounter any opening bracket in the string , we push the index of that element inside stack . For instance we encounter ( at index 0 , so we push 0 inside the stack. Now stack contains [-1,0].\n\nNow , when we encounter any closing bracket , we pop out the topmost element of stack which is 0 here. So stack remains with -1.\n\nAlso, if the stack is empty ,then we have to push the index of the parenthesis that is being popped from stack.\n\nThe length is calculated by current index-topmost index in stack and  a max variable is maintained which is initialised at 0 and keeps track of the maximum length of substring .\n\n\n# Complexity\n- Time complexity: $$O(n)$$ \n<!-- Add your time complexity here, e.g. -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g.  -->\n\n# Code\n```\nclass Solution2 {\n    public int longestValidParentheses(String s) {\n  Stack<Integer>stack= new Stack<>();\n  stack.push(-1);\n  int max=0;\n\n  for(int i=0;i<s.length();i++)\n  {\n    char c= s.charAt(i);\n\n    if(c==\'(\')\n    {\n        stack.push(i);\n    }\n\n    else{\n        stack.pop();\n        if(stack.isEmpty())\n        {\n            stack.push(i);\n        }\n        else{\n            int l=i-stack.peek();\n            max=Math.max(max,len);\n        }\n    }\n  }\n\nreturn max;\n\n    }\n```
['Java']