Last updated on March 7th, 2025 at 10:12 pm
Here, we see the Longest Valid Parentheses LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Dynamic Programming, Stack, String
Level of Question
Hard

Longest Valid Parentheses LeetCode Solution
Table of Contents
1. Problem Statement
Given a string containing just the characters ‘(‘ and ‘)’, return 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
2. Coding Pattern Used in Solution
The coding pattern used in all the provided implementations is “Stack-based Parentheses Matching”. It involves using a stack to keep track of indices of unmatched parentheses and calculating the length of valid parentheses substrings based on the stack’s state.
3. Code Implementation in Different Languages
3.1 Longest Valid Parentheses C++
class Solution { public: int longestValidParentheses(string s) { stack<int> opens; for(int i = 0; i < s.size(); i++) { if(s[i] == '(') opens.push(i); else if(opens.size()) { s[opens.top()] = s[i] = '*'; opens.pop(); } } int curr = 0, res = 0; for(int i = 0; i <= s.size(); i++) { if(s[i] == '*') curr++; else { res = max(res, curr); curr = 0; } } return max(curr, res); } };
3.2 Longest Valid Parentheses Java
class Solution { public int longestValidParentheses(String s) { LinkedList<Integer> stack = new LinkedList<>(); int result = 0; stack.push(-1); for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == ')' && stack.size() > 1 && s.charAt(stack.peek()) == '(') { stack.pop(); result = Math.max(result, i - stack.peek()); } else { stack.push(i); } } return result; } }
3.3 Longest Valid Parentheses JavaScript
var longestValidParentheses = function(s) { let stack = [-1], ans = 0 for (let i = 0; i < s.length; i++) if (s[i] === '(') stack.push(i) else if (stack.length === 1) stack[0] = i else stack.pop(), ans = Math.max(ans, i - stack[stack.length-1]) return ans };
3.4 Longest Valid Parentheses Python
class Solution(object): def longestValidParentheses(self, s): stack = [-1] max_length = 0 for cur_idx, char in enumerate(s): if char == '(': stack.append( cur_idx ) else: stack.pop() if not stack: stack.append( cur_idx ) else: max_length = max(max_length, cur_idx - stack[-1]) return max_length
4. Time and Space Complexity
Time Complexity | Space Complexity | |
C++ | O(n) | O(n) |
Java | O(n) | O(n) |
JavaScript | O(n) | O(n) |
Python | O(n) | O(n) |
- The code efficiently calculates the length of the longest valid parentheses substring using a stack-based approach.
- It has a linear time complexity of O(n) and a linear space complexity of O(n) due to the stack.
- This pattern is a classic example of using a stack to solve problems involving matching or balancing parentheses.