DSA Visualizations | Hello Interview (2024)

Longest Valid Parentheses

s = "())))"

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

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

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

s = ""

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:

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.

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.

This leads us to the following algorithm:

1. 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.

2. 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.

3. 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 1s = "(()())":

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

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

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

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

ReturnWe 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 '(((((((((((').