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

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.