DSA Visualizations | Hello Interview

Longest Valid Parentheses

DESCRIPTION (credit Leetcode.com)

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring. A well-formed parentheses string is one that follows these rules:

Open brackets must be closed by a matching pair in the correct order.

For example, given the string "(()", the longest valid parentheses substring is "()", which has a length of 2. Another example is the string ")()())", where the longest valid parentheses substring is "()()", which has a length of 4.

EXAMPLES

Example 1:
Inputs:


s = "())))"

Output:

(Explanation: The longest valid parentheses substring is "()")

Example 2:
Inputs:


s = "((()()())"

Output:

(Explanation: The longest valid parentheses substring is "(()()())" with a length of 8)

Example 3:
Inputs:


s = ""

Output:

Run your code to see results here

Explanation

At a high level, we can solve this problem by iterating over each index of the string, and then calculating the length of the longest valid parentheses substring that ends at that index. We can then take the maximum of these lengths to get the final answer.

Each time we encounter a closing parenthesis ')', it has the potential to close a valid parentheses substring. In order to calculate the length of the longest valid parentheses substring that ends at a given index, we need to know the index of the last unmatched opening parenthesis '('.

The length of the valid substring ending at the current index can be calculated by taking the difference between the current index and the index of the last unmatched opening parenthesis.

Let's visualize a few examples to understand how that calculation works:

Current index: 2. Last unmatched opening parenthesis at index 0. Length: 2 - 0 = 2

Current index: 3. Last unmatched opening parenthesis at index 1. Length: 3 - 1 = 2

Current index: 5. Last unmatched opening parentheses = 1. Length = 5 - 1 = 4.

If there aren't any unmatched opening parentheses remaining after using the current closing parentheses, then we need to know the "start" of the current valid substring. Setting this value to -1 makes our calculation easier, as we can simply take the difference between the current index and the start of the valid substring to get the length.

Current index: 3. The start of the current valid substring is -1, so length = 3 - (-1) = 4

However, if the closing parenthesis ')' doesn't close any valid substring (as shown below), then we can simply ignore it, and set the start of the current valid substring to the current index.

Current index: 3. But there is no unmatched opening parenthesis. Length: 0

This leads us to the following algorithm:

Initialize a stack. The stack will always contain the index of the last unmatched opening parenthesis, or the "start" of the current valid substring. Initially, the stack will contain -1 as the start of the current valid substring.
Each time we encounter an opening parenthesis '(', we'll push its index onto the stack, which represents the index of the last unmatched opening parenthesis.
Each time we encounter a closing parenthesis ')', we'll do the following:
1. We first pop the top element from the stack, as this closing parenthesis has the potential to close a valid parentheses substring.
2. Now, after popping, there are two possible cases:
  1. The stack is not empty, and the top of the stack represents the index of the last unmatched opening parenthesis. We calculate the length of the valid substring ending at the current index by taking the difference between the current index and the index of the last unmatched opening parenthesis.
  2. The stack is empty. This means that this closing parenthesis was unmatched. We'll update the start of the valid substring to the current index by pushing the current index onto the stack.

Solution

class Solution:
    def longest_valid_parentheses(self, s: str) -> int:
        max_len = 0
        stack = [-1]
        
        for i, char in enumerate(s):
            if char == '(':
                stack.append(i)
            else:
                # first pop the top element
                stack.pop()
                if not stack:
                    # stack is empty. update the start of the valid substring
                    stack.append(i)
                else:
                    # stack is not empty.
                    # we can calculate the length of the valid substring
                    max_len = max(max_len, i - stack[-1])
        
        return max_len

Walkthrough

Example 1 s = "(()())":

Initialization: Stack: [-1]

Traverse the string:

Index 0, '(': Push index 0 onto the stack. Stack: [-1, 0]

Index 1, '(': Push index 1 onto the stack. Stack: [-1, 0, 1]

Index 2, ')': Pop the stack (index 1). Stack: [-1, 0] Calculate length: 2 - 0 = 2

Index 3, '(': Push index 3 onto the stack. Stack: [-1, 0, 3]

Index 4, ')': Pop the stack (index 3). Stack: [-1, 0] Calculate length: 4 - 0 = 4

Index 5, ')': Pop the stack (index 0). Stack: [-1] Calculate length: 5 - (-1) = 6

Return We can return the max of each calculated length, which is 6.

Example 2 s = ")())()()"

Initialization: Stack: [-1]

Traverse the string:

Index 0, ')': Pop the stack (index -1). The stack is empty, so push index 0 onto the stack. Note: We don't need to calculate the length here, as there is no valid substring ending at index 0. Instead, index 0 will be the start of the next valid substring. Stack: [0]

Index 1, '(': Push index 1 onto the stack. Stack: [0, 1]

Index 2, ')': Pop the stack (index 1). Stack: [0] Calculate length: 2 - 0 = 2

Index 3, ')': Pop the stack (index 0). The stack is empty, so push index 3 onto the stack. Note: We don't need to calculate the length here, as there is no valid substring ending at index 3. Instead, index 3 will be the start of the next valid substring. Stack: [3]

Index 4, '(': Push index 4 onto the stack. Stack: [3, 4]

Index 5, ')': Pop the stack (index 4). Stack: [3] Calculate length: 5 - 3 = 2

Index 6, '(': Push index 6 onto the stack. Stack: [3, 6]

Index 7, ')': Pop the stack (index 6). Stack: [3] Calculate length: 7 - 3 = 4

Return We can return the max of each calculated length, which is 4.

Complexity Analysis

Time Complexity: O(n), where n is the length of the input string. We iterate over each character of the string once. At each character, we perform a constant amount of work. Space Complexity: O(n), where n is the length of the input string. The stack can contain at most n elements (for example, if the input string is '(((((((((((').

Next: Overview

Your account is free and you can post anonymously if you choose.

Loading comments...

Back to Home

Eliminating Pairs

Overview

Container With Most Water

3-Sum

Triangle Numbers

Pointers as Regions

Move Zeroes

Sort Colors

Trapping Rain Water

Variable-Length

Overview

Longest Substring Without Repeating Characters

Longest Repeating Character Replacement

Fixed-Length

Overview

Maximum Sum of Subarrays of Size K

Max Points You Can Obtain From Cards

Max Sum of Distinct Subarrays Length k

Overview

Can Attend Meetings

Insert Interval

Non-Overlapping Intervals

Merge Intervals

Employee Free Time

Overview

Valid Parentheses

Decode String

Longest Valid Parentheses

Monotonic Stack

Overview

Daily Temperatures

Largest Rectangle in Histogram

Overview

Linked List Cycle

Palindrome Linked List

Remove Nth Node From End of List

Reorder List

Swap Nodes in Pairs

Overview

Apple Harvest (Koko Eating Bananas)

Search in Rotated Sorted Array

Overview

Kth Largest Element in an Array

K Closest Points to Origin

Find K Closest Elements

Merge K Sorted Lists

Introduction

Binary Trees

Overview

Level Order Sum

Rightmost Node

Zigzag Level Order

Maximum Width of Binary Tree

Graphs

Overview

Minimum Knight Moves

Rotting Oranges

01-Matrix

Bus Routes

Overview

Word Search

Solution Space Trees

Subsets

Generate Parentheses

Combination Sum

Topological Sort

Overview

Course Schedule

Course Schedule II

Fundamentals

Solving a Question with Dynamic Programming

Counting Bits

Decode Ways

Maximal Square

Unique Paths

Longest Increasing Subsequence

Word Break

Maximum Profit in Job Scheduling

Overview

Best Time to Buy and Sell Stock

Gas Station

Jump Game

Overview

Implement Trie Methods

Prefix Matching

Overview

Count Vowels in Substrings

Subarray Sum Equals K

Spiral Matrix

Rotate Image

Set Matrix Zeroes

Decode String

Overview

Longest Valid Parentheses

DESCRIPTION (credit Leetcode.com)

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring. A well-formed parentheses string is one that follows these rules:

Open brackets must be closed by a matching pair in the correct order.

EXAMPLES

Example 1:
Inputs:


s = "())))"

Output:

(Explanation: The longest valid parentheses substring is "()")

Example 2:
Inputs:


s = "((()()())"

Output:

(Explanation: The longest valid parentheses substring is "(()()())" with a length of 8)

Example 3:
Inputs:


s = ""