Similar Problems
Similar Problems not available
Longest Valid Parentheses - Leetcode Solution
Companies:
LeetCode: Longest Valid Parentheses Leetcode Solution
Difficulty: Hard
Topics: string stack dynamic-programming
Problem Description:
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
Example: Input: "(()" Output: 2 Explanation: The longest valid parentheses substring is "()"
Input: ")()())" Output: 4 Explanation: The longest valid parentheses substring is "()()"
Solution:
We can use dynamic programming to solve this problem. Let us define dp[i] as the length of the longest valid parentheses substring ending at index i in the given string.
To compute dp[i], we need to analyze the substring ending at index i. There are two cases:
-
If the substring ends with '(', then dp[i] must be 0, since no valid parentheses substring can end with '('.
-
If the substring ends with ')' we need to consider its corresponding '(' in the string. Let 'j' be the index of the matching opening bracket for the closing bracket at index 'i'. Then, we have two cases:
a. If j-1 >= 0, then dp[i] = dp[j-1] + 2, because the substring from j to i is a valid parenthese substring and we can also add the length of the valid subsequence ending at index j-1.
b. If j-1 < 0, then dp[i] = 2, because the first two characters of the given string form a valid parentheses substring (i.e "()").
We can find the matching opening bracket for a given closing bracket in constant time using a stack. We push the index of the opening bracket onto the stack when we encounter it and pop the last element when we encounter a closing bracket.
The final answer is the maximum element in the dp array.
Pseudo-code for the algorithm:
- Initialize an empty stack and a dp array of length n with all values as 0.
- For i = 0 to n-1: a. If s[i] = '(', push i onto the stack. b. If s[i] = ')' and stack is not empty, pop the top element. i. If stack is empty, dp[i] = i+1, otherwise dp[i] = (i - stack.top()) c. Update the maximum length seen so far and update dp array.
- Return maximum length seen so far.
Time Complexity: O(n), where n is the length of the given string s.
Space Complexity: O(n), where n is the length of the given string s.
Code in Python:
class Solution: def longestValidParentheses(self, s: str) -> int: stack = [-1] max_len = 0 n = len(s) dp = [0] * n for i in range(n): if s[i] == '(': stack.append(i) else: if stack and s[stack[-1]] == '(': stack.pop() if not stack: dp[i] = i+1 else: dp[i] = i - stack[-1] max_len = max(max_len, dp[i]) else: stack.append(i) return max_len
Longest Valid Parentheses Solution Code
1class Solution {
2public:
3 int longestValidParentheses(string s) {
4 // Base case
5 if (s.length() <= 1) {
6 return 0;
7 }
8
9 // Variables to keep track of the maximum length valid parentheses
10 // string and the current length of the valid parentheses string
11 int max_len = 0;
12 int curr_len = 0;
13
14 // Stack to keep track of the indices of the '(' characters
15 stack<int> st;
16
17 // Iterate through the input string
18 for (int i = 0; i < s.length(); i++) {
19 // If the current character is a '(', push its index onto the stack
20 if (s[i] == '(') {
21 st.push(i);
22 }
23 // If the current character is a ')',
24 else {
25 // If the stack is empty, this means that there is no matching
26 // '(' character for the current ')' character, so we reset the
27 // current length of valid parentheses to 0
28 if (st.empty()) {
29 curr_len = 0;
30 }
31 // Otherwise, if the stack is not empty, this means that we have
32 // found a matching '(' character for the current ')' character
33 else {
34 // Pop the top element from the stack
35 st.pop();
36
37 // If the stack is now empty, this means that the current
38 // character is the first ')' character in a valid parentheses
39 // string, so we set the current length of valid parentheses
40 // to be the index of the current character plus 1
41 if (st.empty()) {
42 curr_len = i + 1;
43 }
44 // Otherwise, if the stack is not empty, this means that the
45 // current character is not the first ')' character in a valid
46 // parentheses string, so we set the current length of valid
47 // parentheses to be the difference between the index of the
48 // current character and the top element of the stack (which
49 // is the index of the last '(' character in the valid
50 // parentheses string) plus 1
51 else {
52 curr_len = i - st.top();
53 }
54
55 // Update the maximum length of valid parentheses if necessary
56 if (curr_len > max_len) {
57 max_len = curr_len;
58 }
59 }
60 }
61 }
62
63 // Return the maximum length of valid parentheses
64 return max_len;
65 }
66};