Longest Valid Parentheses LeetCode Solution

Here, We see Longest Valid Parentheses LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc., with different approaches.

List of all LeetCode Solution

Longest Valid Parentheses LeetCode Solution

Longest Valid Parentheses LeetCode Solution

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

Longest Valid Parentheses Leetcode Solution 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);        
    }
};
Code language: C++ (cpp)

Longest Valid Parentheses Leetcode Solution 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;     
    }
}
Code language: Java (java)

Longest Valid Parentheses Leetcode Solution 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    
};
Code language: JavaScript (javascript)

Longest Valid Parentheses Leetcode Solution 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
Code language: Python (python)
Scroll to Top