32. Longest Valid Parentheses
Longest Valid Parentheses
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
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 * 104s[i]is'(', or')'.
This is notionally known as the brute force method and is most definitely the slowest valid option. In this approach, we loop through the supplied string, and create a “potentially valid string” (PVS) every time we encounter an open-parentheses.
We then continue traversing the string until said PVS is correctly closed, at which point we consider the PVS valid, and return the longest one found.
Code:
var longestValidParentheses = function (s) {
if (s.length <= 1) {
return 0;
}
let longestString = 0;
let potentiallyValidStrings = [];
// Loop through the input string
for (let i = 0; i < s.length; i++) {
if (s[i] === '(') {
// Increment all potentially valid strings by 1
potentiallyValidStrings = potentiallyValidStrings.map(
(possibility) => {
possibility.stringLength += 1;
return possibility;
}
);
// Add a potentially valid string starting at the current point
potentiallyValidStrings.push({
start: i,
stringLength: 1,
});
} else {
// Decrease all potentially valid strings by 1
potentiallyValidStrings = potentiallyValidStrings.map(
(possibility) => {
possibility.stringLength -= 1;
return possibility;
}
);
// Run through all of the potentially valid strings that are now correctly closed (and are therefore all valid)
potentiallyValidStrings
.filter((possibility) => possibility.stringLength == 0)
.forEach((possibility) => {
// Store the length of the string (if it's the longest one found so far)
longestString = Math.max(
longestString,
i - possibility.start + 1
);
});
// Remove any now-invalid potential strings
potentiallyValidStrings = potentiallyValidStrings.filter(
(possibility) => possibility.stringLength >= 0
);
}
}
return longestString;
};Whilst the easiest to explain, this is, unfortunately, the most inefficient, as we are not only storing more data, but carrying out far more calculations, than the next approach.
Looking for all of the invalid parentheses. Once we know all of the invalid parentheses, we can then assume that the strings between said invalid parentheses are valid, and thus calculate the biggest of those.
Code:
var longestValidParentheses = function (s) {
if (s.length <= 1) {
return 0;
}
let openParentheses = [];
let invalidParentheses = new Set();
for (let i = 0; i < s.length; i++) {
if (s[i] === '(') {
// Store all opening parentheses
openParentheses.push(i);
} else {
if (openParentheses.length) {
// Remove all successfully closed parentheses
openParentheses.pop();
} else {
invalidParentheses.add(i);
}
}
}
// Store any outstanding unclosed parentheses as invalid
while (openParentheses.length) {
invalidParentheses.add(openParentheses.pop());
}
// If the entire string was valid
if (!invalidParentheses.size) {
return s.length;
} else {
let longestValidString = 0,
currentStringLength = 0;
// Loop through the original string
for (let i = 0; i <= s.length; i++) {
// If this character is a part of a larger valid string
if (i < s.length && !invalidParentheses.has(i)) {
currentStringLength++;
}
// Reached invalid character or the end of the string
else {
// Store the length of this string (if its the longest found)
longestValidString = Math.max(
longestValidString,
currentStringLength
);
currentStringLength = 0;
}
}
return longestValidString;
}
};Computationally this approach is far better, but it’s definitely more difficult to wrap your head around and relies on an assumption that does not seem entirely intuitive (but is evidently correctly, at least in the test cases supplied by LeetCode).
/**
* @param {string} s
* @return {number}
*/
var longestValidParentheses = function(s) {
if (!s || !s.length) { return 0; }
/* We will store the position of every invalid parenthesis.
Once we have that, the solution is simply the longest
subarray between two invalid parentheses */
const invalids = new Set();
/* We stack the opening parentheses as we find them,
and pop them we we meet the corresponding closing
parenthesis. Note that a closing ) always matches the
latest opening ( one, hence the choice of a stack */
const stack = [];
for (let i=0; i<s.length; i++) {
if (s[i] === '(') {
stack.push(i);
} else {
// If we are closing an opening parenthesis, pop it out
if (stack.length) {
stack.pop();
} else {
/* Otherwise there is nothing to close,
hence this parenthesis is invalid */
invalids.add(i);
}
}
}
/* Any remaining opening parenthesis that has not been closed is
automatically invalid */
while (stack.length) {
invalids.add(stack.pop());
}
// Here we just count how many valid in between every invalid
let max = 0, count = 0;
for (let i=0; i<=s.length; i++) {
if (i < s.length && !invalids.has(i)) {
count++;
} else {
max = Math.max(max, count);
count = 0;
}
}
return max;
};The algorithm is simple —
- Loop through the string from left to right and store the counts of both type of parentheses in two variables
leftandright. - If
left == right, it means we have a valid substring. - We can then find if the length of current valid substring (
left + right) is the maximum or not. - If
right > left, it means we have invalid string, and we will resetleftandrightto zero. - Repeat the steps 1-4 looping string from right to left and reset the counters as soon as
left > right.
var longestValidParentheses = function (s) {
// Variable to store the longest valid parentheses
let count = 0;
// Left counter will count the number of '('
let left = 0;
// Right counter will count the number of ')'
let right = 0;
// Loop through the string from left to right.
// This will take care of extra right parentheses
for (let i = 0; i < s.length; i++) {
// Current character
let c = s[i];
if (c === '(') {
left++;
}
if (c === ')') {
right++;
}
// If both left and right are equal,
// it means we have a valid substring
if (left === right) {
count = Math.max(count, left + right);
}
// If right is greater than left,
// it means we need to set both
// counters to zero
if (right > left) {
left = right = 0;
}
}
// Reset left and right
left = right = 0;
// Follow the same approach but now loop the string
// from right to left. This will take care of extra
// left parentheses
for (let i = s.length - 1; i >= 0; i--) {
// Current character
let c = s[i];
if (c === '(') {
left++;
}
if (c === ')') {
right++;
}
// If both left and right are equal,
// it means we have a valid substring
if (left === right) {
count = Math.max(count, left + right);
}
// If right is greater than left,
// it means we need to set both
// counters to zero
if (left > right) {
left = right = 0;
}
}
return count;
};
Time Complexity
Since we are looping the string twice, the time complexity will be O(n).
Space Complexity
We are not using any data structures to store intermediate computations, hence the space complexity will be O(1).
Conclusion
That’s all folks! In this post, we solved LeetCode problem #32. Longest Valid Parentheses
I hope you have enjoyed this post. Feel free to share your thoughts on this.
You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.
In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!
Comments
Post a Comment