Longest Valid Parentheses | JS, Python, Java, C++ | Easy Stack Solution w/ Explanation
(Note: This is part of a series of Leetcode solution explanations. If you like this solution or find it useful, please upvote this post.)\n\n---\n\n#### Idea:\n
*(Note: This is part of a series of Leetcode solution explanations. If you like this solution or find it useful,* ***please upvote*** *this post.)*\n\n---\n\n#### ***Idea:***\n\nOne of the key things to realize about valid parentheses strings is that they\'re entirely self-satisfied, meaning that while you can have one substring that is entirely inside another, you can\'t have two substrings that only partially overlap.\n\nThis means that we can use a **greedy O(N) time complexity** solution to this problem without the need for any kind of backtracking. In fact, we should be able to use a very standard stack-based valid parentheses string algorithm with just three very minor modifications.\n\nIn a stadard valid parentheses string algorithm, we iterate through the string (**S**) and push the index (**i**) of any **\'(\'** to our **stack**. Whenever we find a **\')\'**, we match it with the last entry on the **stack** and pop said entry off. We know the string is not valid if we find a **\')\'** while there are no **\'(\'** indexes in the **stack** with which to match it, and also if we have leftover **\'(\'** in the **stack** when we reach the end of **S**.\n\nFor this problem, we will need to add in a step that updates our answer (**ans**) when we close a parentheses pair. Since we stored the index of the **\'(\'** in our stack, we can easily find the difference between the **\')\'** at **i** and the last entry in the **stack**, which should be the length of the valid substring which was just closed.\n\nBut here we run into a problem, because consecutive valid substrings can be grouped into a larger valid substring (ie, **\'()()\' = 4**). So instead of counting from the *last* **stack** entry, we should actually count from the *second to last* entry, to include any other valid closed substrings since the most recent **\'(\'** that will still remain after we pop the just-matched last **stack** entry off.\n\nThis, of course, brings us to the second and third changes. Since we\'re checking the second to last **stack** entry, what happens in the case of **\'()()\'** when you close the second valid substring yet there\'s only the one **stack** entry left at the time?\n\nTo avoid this issue, we can just wrap the entire string in another imaginary set of parentheses by starting with **stack = [-1]**, indicating that there\'s an imaginary **\'(\'** just before the beginning of the string at **i = 0**.\n\nThe other issue is that we will want to continue even if the string up to **i** becomes invalid due to a **\')\'** appearing when the **stack** is "empty", or in this case has only our imaginary index left. In that case, we can just effectively restart our **stack** by updating our imaginary **\'(\'** index (**stack[0] = i**) and continue on.\n\nThen, once we reach the end of **S**, we can just **return ans**.\n\n---\n\n#### ***Implementation:***\n\nThere are only minor differences in the code for all four languages.\n\n---\n\n#### ***Javascript Code:***\n\nThe best result for the code below is **76ms / 39.9MB** (beats 99% / 78%).\n```javascript\nvar longestValidParentheses = function(S) {\n    let stack = [-1], ans = 0\n    for (let i = 0; i < S.length; i++)\n        if (S[i] === \'(\') stack.push(i)\n        else if (stack.length === 1) stack[0] = i\n        else stack.pop(), ans = Math.max(ans, i - stack[stack.length-1])\n    return ans\n};\n```\n\n---\n\n#### ***Python Code:***\n\nThe best result for the code below is **40ms / 14.6MB** (beats 88% / 71%).\n```python\nclass Solution:\n    def longestValidParentheses(self, S: str) -> int:\n        stack, ans = [-1], 0\n        for i in range(len(S)):\n            if S[i] == \'(\': stack.append(i)\n            elif len(stack) == 1: stack[0] = i\n            else:\n                stack.pop()\n                ans = max(ans, i - stack[-1])\n        return ans\n```\n\n---\n\n#### ***Java Code:***\n\nThe best result for the code below is **2ms / 38.7MB** (beats 69% / 94%).\n```java\nclass Solution {\n    public int longestValidParentheses(String S) {\n        Stack<Integer> stack = new Stack<>();\n        stack.push(-1);\n        int ans = 0;\n        for (int i = 0; i < S.length(); i++)\n            if (S.charAt(i) == \'(\') stack.push(i);\n            else {\n                stack.pop();\n                if (stack.isEmpty()) stack.push(i);\n                else ans = Math.max(ans, i - stack.peek());\n            }\n        return ans;\n    }\n}\n```\n\n---\n\n#### ***C++ Code:***\n\nThe best result for the code below is **0ms / 7.1MB** (beats 100% / 71%).\n```c++\nclass Solution {\npublic:\n    int longestValidParentheses(string S) {\n        vector<int> stack = {-1};\n        int ans = 0;\n        for (int i = 0; i < S.size(); i++)\n            if (S[i] == \'(\') stack.push_back(i);\n            else if (stack.size() == 1) stack[0] = i;\n            else {\n                stack.pop_back();\n                ans = max(ans, i - stack.back());\n            }\n        return ans;\n    }\n};\n```
[]