Skip to main content

longest-valid-parentheses

Problem Description​

Given a string containing just the characters '(' and ')', return the length of the longest valid (well-formed) parentheses substring

Examples​

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

Constraints​

  • 1≤nums.length≤1051 \leq \text{nums.length} \leq 105

Solution for Longest Valid Parentheses​

Intuition​

The intuition behind the given code is to use a stack to efficiently track the indices of opening parentheses.

Approach​

  • It initializes a variable maxCount to 0 to store the length of the longest valid parentheses substring.

  • It initializes a stack (st) and pushes -1 onto the stack. The stack is used to keep track of the indices of opening parentheses.

  • It iterates through each character in the input string s.

  • If the current character is an opening parenthesis '(', it pushes its index onto the stack.

  • If the current character is a closing parenthesis ')', it pops the top element from the stack, representing the index of the matching opening parenthesis.

  • If the stack becomes empty after popping, it pushes the current index onto the stack (unmatched closing parenthesis).

  • If the stack is not empty, it calculates the length of the valid parentheses substring by subtracting the index of the matching opening parenthesis from the current index. It updates maxCount with the maximum length encountered so far.

  • After iterating through all characters, it returns maxCount, representing the length of the longest valid parentheses substring.

Code in Different Languages​

Written by @parikhitkurmi
//python

class Solution:
def longestValidParentheses(self, s: str) -> int:
max_length = 0
stck=[-1] # initialize with a start index
for i in range(len(s)):
if s[i] == '(':
stck.append(i)
else:
stck.pop()
if not stck: # if popped -1, add a new start index
stck.append(i)
else:
max_length=max(max_length, i-stck[-1]) # update the length of the valid substring
return max_length

Complexity

  • Time complexity: $O(n)$ time complexity as we iterate over the string

  • Space complexity: $O(n)$ space complexity because we used stack

References​