LeetCode 32: Longest Valid Parentheses Solution
Master LeetCode problem 32 (Longest Valid Parentheses), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
32. Longest Valid Parentheses
Problem Explanation
Explanation:
To solve this problem, we can use a stack to keep track of the indices of the opening parentheses. We iterate through the input string and whenever we encounter an opening parenthesis, we push its index onto the stack. When we encounter a closing parenthesis, we check if the stack is empty. If it is empty, we update the starting index for the next valid substring. If the stack is not empty, we pop the top index from the stack and calculate the length of the current valid substring.
We also need to handle cases where there are unmatched parentheses. To do this, we initialize the starting index as -1 and update it whenever we encounter a closing parenthesis with an empty stack.
Finally, the length of the longest valid substring will be the maximum difference between the current index and the starting index.
Time Complexity: O(n) - where n is the length of the input string. Space Complexity: O(n) - for the stack to store indices.
:
Solution Code
class Solution {
public int longestValidParentheses(String s) {
int maxLen = 0;
Stack<Integer> stack = new Stack<>();
stack.push(-1);
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push(i);
} else {
stack.pop();
if (stack.isEmpty()) {
stack.push(i);
} else {
maxLen = Math.max(maxLen, i - stack.peek());
}
}
}
return maxLen;
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 32 (Longest Valid Parentheses)?
This page provides optimized solutions for LeetCode problem 32 (Longest Valid Parentheses) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 32 (Longest Valid Parentheses)?
The time complexity for LeetCode 32 (Longest Valid Parentheses) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 32 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 32 in Java, C++, or Python.