(JAVA)Effective ⭐️ Longest Valid Parentheses Algorithm: O(n) Time Complexity with Stack✅🔥🚀
Intuition\nThe initial idea is to use a stack to keep track of the positions of opening parentheses in the string. This helps in identifying valid pairs of pare
# Intuition\nThe initial idea is to use a stack to keep track of the positions of opening parentheses in the string. This helps in identifying valid pairs of parentheses and finding the longest sequence of them.\n\n# Approach\nAlgorithm.\n\ncreate a stack with -1 as left end point.\nIterate over all the characters of string from left to right.\nif current character is opening bracket push its index to stack.\nif current character is closing bracket.\n- pop from stack\n- if stack is empty then push current index as new left end point\n- else we found a valid expression between current index and left end point which is top element of stack\n# Complexity\n- Time complexity:\nO(n) time complexity as we iterate over the string\n\n- Space complexity:\nO(n) space complexity because we used stack \n\n# Code\n```\nclass Solution {\n    public int longestValidParentheses(String s) {\n      Stack<Integer> stack = new Stack<>();\n      stack.push(-1);\n      int max=0;\n      for(int i=0;i<s.length();i++){\n        Character ch = s.charAt(i);\n        if(ch == \'(\'){\n            stack.push(i);\n        }\n        else{\n            stack.pop();\n            if(stack.isEmpty()){\n                stack.push(i);\n            }\n            max = Math.max(max,i-stack.peek());\n        }\n      }\n    return max;\n    }\n}\n```
['Stack', 'Java']