Longest Valid Parentheses - LeetCode
Problem statement
Given a string containing just the characters '(' and ')', return the length of the longest valid (well-formed) parentheses substring.
Problem statement taken from: https://leetcode.com/problems/longest-valid-parentheses
Example 1:
Input: s = '(()'
Output: 2
Explanation: The longest valid parentheses substring is '()'.
Example 2:
Input: s = ')()())'
Output: 4
Explanation: The longest valid parentheses substring is '()()'.
Example 3:
Input: s = ''
Output: 0
Constraints:
- 0 <= s.length <= 3 * 10^4
- s[i] is '(', or ')'
Solutions for Longest Valid Parentheses
Approach 1: Brute Force
The brute force approach is to generate all the substrings and check whether every string is valid parentheses. If the substring is valid and the length exceeds the maximum length seen so far, then update the maximum length. We return this maximum length as the longest valid parentheses.
The problem with this approach is the time complexity which is O(n^3). Three nested for loops will be used. The first two will generate all the substrings, and the third inner loop will verify whether the substring is valid parentheses.
Approach 2: Using Stack
An efficient way to solve the longest valid parentheses is using a Stack. The solution is similar to our approach in valid parentheses problem. Instead of pushing the open brackets ( to the stack, we push the indexes of the opening brackets.
The algorithm for this approach is as follows:
- initialize stack<int> st
// push -1 to the stack to provide the base
// for the next valid set of parentheses
st.push(-1)
- set result = 0
- loop for i = 0; i < str.size(); i++
// if opening bracket, push the index i
- if str[i] == '('
- st.push(i)
- else
// if str[i] == ')'
// pop the last encountered opening bracket's index
- if !st.empty()
- st.pop()
- end if
// if the length formed with the base of the current valid substring
// is more than max so far
- if !st.empty
- set result = max(result, i - st.top())
- else
- st.push(i)
- end if
- end if
- end for
- return result
A C++ snippet of this algorithm is as below:
int longestValidParentheses(string s) {
stack<int> stk;
stk.push(-1);
int result = 0;
for (int i = 0; i < str.size(); i++) {
if (str[i] == '(') {
stk.push(i);
} else {
if (!stk.empty()) {
stk.pop();
}
if (!stk.empty()) {
result = max(result, i - stk.top());
} else {
stk.push(i);
}
}
}
return result;
}
The time complexity of this approach is O(n) because we are iterating over the string once. The space complexity is also O(n), as we used an additional data structure, Stack.
Approach 3: Using left and right counters
Using two counters, we can solve this problem in O(1) time.
The idea is to scan the string from left to right.
We keep track of the number of open and closed braces using left and right counters. We increment the left and right counter by 1 when identifying an opening
(and closing)braces.When the left and right counters are equal, the length of the current substring is calculated. If it exceeds the previous longest valid parentheses, we update the result with the current substring length.
At any point while scanning, if the right counter value exceeds the left counter, the substring is not a valid parentheses string. We set the left and right counters to 0.
We then scan the string from right to left and repeat similar steps above.
Let's check the algorithm for this approach.
Algorithm
- set left, right, maxLength = 0
n = s.length
- loop for i = 0; i < n; i++
- if s[i] == '('
- increment left: left++
- else
- increment right: right++
- end if
- if left == right
- update maxLength: maxLength = max(maxLength, 2 * right)
- else if right > left
- set left, right = 0, 0
- end if
- end for
- set left, right = 0, 0
- loop for i = 0; i < n; i++
- if s[i] == '('
- increment left: left++
- else
- increment right: right++
- end if
- if left == right
- update maxLength: maxLength = max(maxLength, 2 * right)
- else if left > right
- set left, right = 0, 0
- end if
- end for
- return maxLength
The time complexity of the above approach is O(n), and the space complexity is O(1).
Check out our solutions in C++, Golang, and Javascript.
C++ solution
class Solution {
public:
// Main function to return the length of
// the longest valid parentheses
int longestValidParentheses(string s) {
int left = 0, right = 0, maxLength = 0;
int n = s.length();
// iterate the string from left to right
for(int i = 0; i < n; i++) {
if(s[i] == '(') {
left++;
} else {
right++;
}
// if left is equal to right, we found a
// valid parentheses substring
if(left == right) {
maxLength = max(maxLength, 2 * right);
} else if (right > left) {
// reset the left and right counter when we have
// invalid parentheses substring
left = 0;
right = 0;
}
}
left = 0;
right = 0;
// iterate the string from right to left
for(int i = n - 1; i >= 0; i--) {
if(s[i] == '(') {
left++;
} else {
right++;
}
// if left is equal to right, we found a
// valid parentheses substring
if(left == right) {
maxLength = max(maxLength, 2 * right);
} else if (left > right) {
// reset the left and right counter when we have
// invalid parentheses substring
left = 0;
right = 0;
}
}
return maxLength;
}
};Golang solution
// Main function to return the length of
// the longest valid parentheses
func longestValidParentheses(s string) int {
left, right, maxLength := 0, 0, 0
n := len(s)
// iterate the string from left to right
for i := 0; i < n; i++ {
if s[i] == '(' {
left++
} else {
right++
}
// if left is equal to right, we found a
// valid parentheses substring
if left == right {
maxLength = max(maxLength, 2 * right)
} else if (right > left) {
// reset the left and right counter when we have
// invalid parentheses substring
left = 0
right = 0
}
}
left = 0
right = 0
// iterate the string from right to left
for i := n - 1; i >= 0; i-- {
if s[i] == '(' {
left++
} else {
right++
}
// if left is equal to right, we found a
// valid parentheses substring
if left == right {
maxLength = max(maxLength, 2 * right)
} else if (left > right) {
// reset the left and right counter when we have
// invalid parentheses substring
left = 0
right = 0
}
}
return maxLength
}
func max(a, b int) int {
if a > b {
return a
}
return b
}JavaScript solution
// Main function to return the length of
// the longest valid parentheses
var longestValidParentheses = function(s) {
let left = 0, right = 0, maxLength = 0;
let n = s.length;
// iterate the string from left to right
for(let i = 0; i < n; i++) {
if(s[i] == '(') {
left++;
} else {
right++;
}
// if left is equal to right, we found a
// valid parentheses substring
if(left == right) {
maxLength = Math.max(maxLength, 2 * right);
} else if (right > left) {
// reset the left and right counter when we have
// invalid parentheses substring
left = 0;
right = 0;
}
}
left = 0;
right = 0;
// iterate the string from right to left
for(let i = n - 1; i >= 0; i--) {
if(s[i] == '(') {
left++;
} else {
right++;
}
// if left is equal to right, we found a
// valid parentheses substring
if(left == right) {
maxLength = Math.max(maxLength, 2 * right);
} else if (left > right) {
// reset the left and right counter when we have
// invalid parentheses substring
left = 0;
right = 0;
}
}
return maxLength;
};Dry Run
Let's dry-run our algorithm to see how the solution works.
Input: s = ')()())'
Step 1: set left = 0, right = 0, maxLength = 0
n = s.size()
= 6
Step 2: loop for i = 0; i < n
0 < 6
true
if s[i] == '('
s[0] == '('
')' == '('
false
else
right++
right = 1
if left == right
0 == 1
false
else if right > left
1 > 0
true
left = 0
right = 0
i++
i = 1
Step 3: loop for i < n
1 < 6
true
if s[i] == '('
s[1] == '('
'(' == '('
true
left++
left = 1
if left == right
1 == 0
false
else if right > left
0 > 1
false
i++
i = 2
Step 4: loop for i < n
2 < 6
true
if s[i] == '('
s[2] == '('
')' == '('
false
else
right++
right = 1
if left == right
1 == 1
true
maxLength = max(maxLength, 2 * right)
= max(0, 2 * 1)
= max(0, 2)
= 2
i++
i = 3
Step 5: loop for i < n
3 < 6
true
if s[i] == '('
s[3] == '('
'(' == '('
true
left++
left = 2
if left == right
2 == 1
false
else if right > left
1 > 2
false
i++
i = 4
Step 6: loop for i < n
4 < 6
true
if s[i] == '('
s[4] == '('
')' == '('
false
else
right++
right = 2
if left == right
2 == 2
true
maxLength = max(maxLength, 2 * right)
= max(2, 2 * 2)
= max(2, 4)
= 4
i++
i = 5
Step 7: loop for i < n
5 < 6
true
if s[i] == '('
s[5] == '('
')' == '('
false
else
right++
right = 3
if left == right
2 == 3
false
else
left = 0
right = 0
i++
i = 6
Step 8: loop for i < n
6 < 6
false
Step 9: left = 0
right = 0
Step 10: loop for i = n - 1; i >= 0
i = 6 - 1 = 5
i >= 0
5 >= 0
true
if s[i] == '('
s[5] == '('
')' == '('
false
else
right++
right = 1
if left == right
0 == 1
false
else if left > right
0 > 1
false
i--
i = 4
Step 11: loop for i >= 0
4 >= 0
true
if s[i] == '('
s[4] == '('
')' == '('
false
else
right++
right = 2
if left == right
0 == 2
false
else if left > right
0 > 2
false
i--
i = 3
Step 12: loop for i >= 0
3 >= 0
true
if s[i] == '('
s[3] == '('
'(' == '('
true
left++
left = 1
if left == right
1 == 2
false
else if left > right
1 > 2
false
i--
i = 2
Step 13: loop for i >= 0
2 >= 0
true
if s[i] == '('
s[2] == '('
')' == '('
false
else
right++
right = 3
if left == right
1 == 3
false
else if left > right
1 > 3
false
i--
i = 1
Step 14: loop for i >= 0
1 >= 0
true
if s[i] == '('
s[1] == '('
'(' == '('
true
left++
left = 2
if left == right
2 == 3
false
else if left > right
2 > 3
false
i--
i = 0
Step 15: loop for i >= 0
0 >= 0
true
if s[i] == '('
s[1] == '('
')' == '('
false
else
right++
right = 4
if left == right
2 == 4
false
else if left > right
2 > 4
false
i--
i = -1
Step 16: loop for i >= 0
-1 >= 0
false
Step 17: return maxLength
We return the answer as 4.