Longest Valid Parentheses LeetCode Solution

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

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)