Easy to understand DP Solution || O(N) || 5 lines
Intuition\nThe problem asks for the length of the longest valid parentheses substring in a given string. To solve this problem, we can use dynamic programming. 
# Intuition\nThe problem asks for the length of the longest valid parentheses substring in a given string. To solve this problem, we can use dynamic programming. The idea is to maintain a dynamic programming array `dp`, where `dp[i]` represents the length of the longest valid parentheses substring ending at index `i` of the input string. We can initialize `dp` with zeros and then iterate through the string to update `dp` as we find valid parentheses substrings.\n\n# Approach\n1. Initialize a dynamic programming array `dp` of size `s.size() + 1` and initialize all elements to 0.\n2. Initialize a variable `ans` to 0, which will store the maximum length of valid parentheses substring found so far.\n3. Iterate through the characters of the input string `s` from left to right, starting from the second character (index 1).\n   - If the current character is \')\':\n     - Check if there is a valid opening parenthesis \'(\' that can be matched with the current closing parenthesis \')\'.\n     - To do this, check if the character before the current closing parenthesis (at index `i`) is an opening parenthesis \'(\', and if the character just before the opening parenthesis (at index `i - dp[i] - 1`) is also an opening parenthesis \'(\'.\n     - If the conditions are met, update `dp[i + 1]` as follows:\n       - `dp[i + 1] = dp[i] + 2 + dp[i - dp[i] - 1]`\n       - Here, `dp[i]` represents the length of valid parentheses substring ending at the previous character, and `dp[i - dp[i] - 1]` represents the length of valid parentheses substring just before the opening parenthesis that matches with the current closing parenthesis.\n   - Update `ans` with the maximum value between the current `ans` and `dp[i + 1]`.\n4. After iterating through the entire string, `ans` will contain the length of the longest valid parentheses substring in the input string.\n5. Return `ans` as the result.\n\n# Complexity\n- Time complexity: O(n), where n is the length of the input string `s`. We iterate through the string once, and for each character, we perform constant time operations.\n- Space complexity: O(n), as we use a dynamic programming array `dp` of the same length as the input string.\n\n# Code\n```cpp\nclass Solution {\npublic:\n    int longestValidParentheses(string s) {\n        vector<int> dp(s.size() + 1, 0);\n        int ans = 0;\n        for (int i = 1; i < s.size(); i++) {\n            if (s[i] == \')\' && (i - dp[i] - 1) >= 0 && s[i - dp[i] - 1] == \'(\')\n                dp[i + 1] = dp[i] + 2 + dp[i - dp[i] - 1];\n            ans = max(ans, dp[i + 1]);\n        }\n        return ans;\n    }\n};
['C++']