✅ 🔥 0 ms Runtime Beats 100% User🔥||  Code Idea ✅ ||  Algorithm & Solving Step  ✅ ||
\n\n\n\n\u2705  IF YOU LIKE THIS SOLUTION, PLEASE UPVOTE AT THE END \u2705 :\n\n### Intuition :\nTo find the longest valid parentheses substring, we need to eff
![Screenshot 2024-12-05 at 6.13.36\u202FPM.png](https://assets.leetcode.com/users/images/b50ab92b-9720-4602-a686-b3808cbdedcc_1733402684.404483.png)\n\n![Screenshot 2024-12-05 at 6.12.14\u202FPM.png](https://assets.leetcode.com/users/images/c477dead-2f7b-464a-91a3-3527215d4865_1733402697.9628787.png)\n\n\u2705  IF YOU LIKE THIS SOLUTION, PLEASE UPVOTE AT THE END \u2705 :\n\n### **Intuition** :\nTo find the longest valid parentheses substring, we need to efficiently identify matching pairs of parentheses. There are several approaches to solve this, but two prominent ones are:\n1. **Using a Stack**: Track unmatched opening and closing parentheses using indices.\n2. **Dynamic Programming**: Use a DP array to record the length of valid substrings ending at each position.\n\n---\n\n### **Approach 1: Stack-Based Solution** :\n\n#### **Idea** :\n- Use a stack to keep track of indices of unmatched parentheses.\n- When encountering `\')\'`, check if the stack has an unmatched `\'(\'`. If so, calculate the length of the valid substring.\n\n#### **Algorithm** :\n1. Initialize a stack and push `-1` as a base index.\n2. Traverse the string:\n   - If `\'(\'`, push its index onto the stack.\n   - If `\')\'`:\n     - Pop from the stack.\n     - If the stack is not empty, calculate the length of the valid substring (`i - stack[-1]`).\n     - If empty, push the current index.\n3. Return the maximum length.\n\n---\n\n#### **Code** :\n\n##### **C++** :\n```cpp\n#include <stack>\n#include <string>\n#include <algorithm>\nusing namespace std;\n\nclass Solution {\npublic:\n    int longestValidParentheses(string s) {\n        stack<int> st;\n        st.push(-1);  // Base index\n        int maxLength = 0;\n\n        for (int i = 0; i < s.size(); i++) {\n            if (s[i] == \'(\') {\n                st.push(i);\n            } else {\n                st.pop();\n                if (st.empty()) {\n                    st.push(i);\n                } else {\n                    maxLength = max(maxLength, i - st.top());\n                }\n            }\n        }\n        return maxLength;\n    }\n};\n```\n\n##### **Java** :\n```java\nimport java.util.Stack;\n\nclass Solution {\n    public int longestValidParentheses(String s) {\n        Stack<Integer> stack = new Stack<>();\n        stack.push(-1);  // Base index\n        int maxLength = 0;\n\n        for (int i = 0; i < s.length(); i++) {\n            if (s.charAt(i) == \'(\') {\n                stack.push(i);\n            } else {\n                stack.pop();\n                if (stack.isEmpty()) {\n                    stack.push(i);\n                } else {\n                    maxLength = Math.max(maxLength, i - stack.peek());\n                }\n            }\n        }\n        return maxLength;\n    }\n}\n```\n\n##### **Python** :\n```python\nclass Solution:\n    def longestValidParentheses(self, s: str) -> int:\n        stack = [-1]  # Base index\n        max_length = 0\n\n        for i, char in enumerate(s):\n            if char == \'(\':\n                stack.append(i)\n            else:\n                stack.pop()\n                if not stack:\n                    stack.append(i)\n                else:\n                    max_length = max(max_length, i - stack[-1])\n        \n        return max_length\n```\n\n---\n\n### **Approach 2: Dynamic Programming** :\n\n#### **Idea** :\n- Use a DP array where `dp[i]` stores the length of the longest valid parentheses substring ending at `i`.\n- Update the DP array based on matching parentheses.\n\n#### **Algorithm** :\n1. Initialize `dp` array with zeros.\n2. Traverse the string:\n   - If `s[i] == \')\'` and `s[i-1] == \'(\'`, update `dp[i] = dp[i-2] + 2`.\n   - If `s[i] == \')\'` and `s[i-1] == \')\'`, check for a matching `(` at `i - dp[i-1] - 1` and update.\n3. Return the maximum in `dp`.\n\n---\n\n#### **Code** :\n\n##### **C++** :\n```cpp\n#include <vector>\n#include <string>\n#include <algorithm>\nusing namespace std;\n\nclass Solution {\npublic:\n    int longestValidParentheses(string s) {\n        int n = s.size();\n        vector<int> dp(n, 0);\n        int maxLength = 0;\n\n        for (int i = 1; i < n; i++) {\n            if (s[i] == \')\') {\n                if (s[i - 1] == \'(\') {\n                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;\n                } else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == \'(\') {\n                    dp[i] = dp[i - 1] + (i - dp[i - 1] >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;\n                }\n                maxLength = max(maxLength, dp[i]);\n            }\n        }\n        return maxLength;\n    }\n};\n```\n\n##### **Java** :\n```java\nclass Solution {\n    public int longestValidParentheses(String s) {\n        int n = s.length();\n        int[] dp = new int[n];\n        int maxLength = 0;\n\n        for (int i = 1; i < n; i++) {\n            if (s.charAt(i) == \')\') {\n                if (s.charAt(i - 1) == \'(\') {\n                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;\n                } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == \'(\') {\n                    dp[i] = dp[i - 1] + (i - dp[i - 1] >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;\n                }\n                maxLength = Math.max(maxLength, dp[i]);\n            }\n        }\n        return maxLength;\n    }\n}\n```\n\n##### **Python** :\n```python\nclass Solution:\n    def longestValidParentheses(self, s: str) -> int:\n        dp = [0] * len(s)\n        max_length = 0\n\n        for i in range(1, len(s)):\n            if s[i] == \')\':\n                if s[i - 1] == \'(\':\n                    dp[i] = (dp[i - 2] if i >= 2 else 0) + 2\n                elif i - dp[i - 1] > 0 and s[i - dp[i - 1] - 1] == \'(\':\n                    dp[i] = dp[i - 1] + (dp[i - dp[i - 1] - 2] if i - dp[i - 1] >= 2 else 0) + 2\n                max_length = max(max_length, dp[i])\n        \n        return max_length\n```\n\n---\n\n### **Complexity Analysis** :\n\n#### **Stack-Based Solution** :\n- **Time Complexity**: O(n) \u2014 Each character is pushed and popped from the stack once.\n- **Space Complexity**: O(n) \u2014 The stack holds indices.\n\n#### **Dynamic Programming Solution** :\n- **Time Complexity**: O(n) \u2014 Single pass through the string.\n- **Space Complexity**: O(n) \u2014 DP array of size n.\n---\n![image.png](https://assets.leetcode.com/users/images/577cbc64-bdf8-42cd-aff4-6c1c2371f988_1733402880.575761.png)\n
['String', 'Dynamic Programming', 'Stack', 'C++', 'Java', 'Python3']