Longest Valid Parentheses

To find the length of the longest valid parentheses substring in a given string s, you can use a stack to keep track of the indexes of the characters and follow these steps:

  1. Initialize Variables: Initialize a variable max_length to keep track of the maximum length of the valid parentheses substring and set it to 0. Initialize a stack and push -1 onto it.

  2. Iterate through the String: Iterate through the string s and for each character:

    • If the character is ‘(’, push its index onto the stack.
    • If the character is ‘)’, pop an element from the stack.
      • If the stack is not empty after the pop, update max_length with the maximum of its current value and the difference between the current index and the index at the top of the stack.
      • If the stack is empty after the pop, push the current index onto the stack.

  3. Return the Result: Return the value of max_length.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        max_length = 0
        stack = [-1]  # Initialize stack with -1

        # Iterate through the string
        for i in range(len(s)):
            if s[i] == '(':
                stack.append(i)  # Push index of '(' onto the stack
            else:
                stack.pop()  # Pop an element from the stack
                if stack:
                    # Update max_length if stack is not empty
                    max_length = max(max_length, i - stack[-1])
                else:
                    # Push current index onto the stack if it's empty
                    stack.append(i)

        return max_length

This solution has a time complexity of (O(n)) and space complexity of (O(n)), where (n) is the length of the string. It iterates through the string once and uses a stack to keep track of the indexes.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        maxans = 0
        stack = [-1]
        for i in range(len(s)):
            if s[i] == '(':
                stack.append(i)
            else:
                stack.pop()
                if not stack:
                    stack.append(i)
                else:
                    maxans = max(maxans, i - stack[-1])
        return maxans

Identifying Problem Isomorphism

“Longest Valid Parentheses” shares similarities with “Minimum Remove to Make Valid Parentheses”.

In “Minimum Remove to Make Valid Parentheses”, the task is to remove the minimum number of parentheses so that any remaining string is valid. This is closely related to the task in “Longest Valid Parentheses”, where the aim is to find the length of the longest valid parentheses substring. Both problems require a good understanding of stack operations or a well-optimized dynamic programming solution for an efficient resolution.

“Longest Valid Parentheses” focuses on the maximal length of a well-formed parentheses substring, which can be considered as a bit more straightforward. “Minimum Remove to Make Valid Parentheses” is a bit more complex, as it needs to deal with the operation of removal to make the parentheses string valid, and to achieve this with minimum removals.

10 Prerequisite LeetCode Problems

“Longest Valid Parentheses” requires a good understanding of string parsing, stack data structure, and dynamic programming. Here are 10 problems to build up to it:

  1. “Valid Parentheses” (LeetCode Problem #20): This is a simpler version of the problem where you just need to validate if the parentheses are balanced.

  2. “Min Stack” (LeetCode Problem #155): This problem will help you understand how to use a stack to keep track of the minimum element.

  3. “Binary Tree Inorder Traversal” (LeetCode Problem #94): Although this problem is about binary trees, it uses a stack for the traversal, which is a useful concept.

  4. “Implement Queue using Stacks” (LeetCode Problem #232): This problem gives practice on manipulating stacks.

  5. “Decode String” (LeetCode Problem #394): This problem involves a similar concept of parsing a string and making use of a stack.

  6. “Remove Outermost Parentheses” (LeetCode Problem #1021): This problem involves removing parentheses based on certain conditions, which is a useful concept for the problem at hand.

  7. “Climbing Stairs” (LeetCode Problem #70): This problem introduces the concept of dynamic programming, a key concept for the problem at hand.

  8. “Best Time to Buy and Sell Stock” (LeetCode Problem #121): This problem also makes use of dynamic programming and introduces the concept of maintaining a “running maximum or minimum.”

  9. “Balanced Binary Tree” (LeetCode Problem #110): The idea of a balanced tree is conceptually similar to the idea of balanced parentheses.

  10. “Longest Increasing Subsequence” (LeetCode Problem #300): This problem introduces a more advanced form of dynamic programming which is useful for the problem at hand.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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

Problem Classification

“Longest Valid Parentheses” problem can be classified under the Balance and Symmetry Analysis category. This is about finding the longest stretch of balanced and properly nested parentheses. This could be relevant in fields like syntax analysis in programming languages or molecular structure analysis in chemistry, where the balance and symmetry of certain elements or compounds are critical.

Language Agnostic Coding Drills

This solution to finding the longest valid parentheses uses concepts such as strings, lists (as stack), conditionals, iteration, list append, and list pop operations. The problem-solving approach involves using a stack to track indices of parentheses while checking the validness of the parentheses substring.

  1. Understanding of Strings: Understanding of strings is crucial here as we are dealing with a string of parentheses. The input string consists of only ‘(’ and ‘)’ characters.

  2. Working with Lists as Stacks: In this solution, a list is used to implement a stack data structure. Understanding how to use lists as stacks (Last In First Out - LIFO) is essential. Key operations include append (push into stack) and pop (remove from stack).

  3. Iterating over a string: The solution involves iterating over the string and performing certain actions based on the current character.

  4. Using Conditionals: Based on the character in the string (whether it’s an opening or closing parenthesis), different actions are performed. Understanding if-else conditional statements is key here.

  5. Indexing in Lists: The solution makes use of indexing to access elements in the stack (which is implemented as a list). It uses both positive indexing (from the start) and negative indexing (from the end).

  6. Updating variables: The solution involves updating the value of the max_length variable, which keeps track of the maximum length of valid parentheses string found so far.

Arranging these concepts in increasing level of difficulty:

  1. Understanding of Strings
  2. Iterating over a string
  3. Using Conditionals
  4. Working with Lists as Stacks
  5. Indexing in Lists
  6. Updating variables

Problem-solving approach:

The algorithm uses a stack to keep track of the indices of the parentheses in the string. It initializes the stack with -1 to denote the base of the ‘virtual’ parentheses string (a technique used to handle edge cases).

  1. The algorithm starts by iterating through the string, one character at a time.

  2. If the current character is an opening parenthesis, it’s index is added to the stack.

  3. If the current character is a closing parenthesis, the top element (index) is popped from the stack, indicating that a pair has been completed.

  4. The stack’s top is then checked again. If it’s empty, this means the closing parenthesis doesn’t have a corresponding opening parenthesis, so it adds the current index as a new base index to the stack.

  5. If the stack is not empty, it calculates the length of the valid string of parentheses by subtracting the topmost index in the stack from the current index. If this length is greater than the current max_length, it updates max_length.

  6. The algorithm repeats steps 2-5 until it has processed all characters in the string. It then returns the max_length value, which represents the length of the longest valid parentheses substring.

Targeted Drills in Python

  1. Understanding of Strings:

    Problem Statement: Write a Python function to check if a string contains only ‘(’ and ‘)’ characters.

    1
2
3
4
5

    def valid_parentheses_string(s):
    for char in s:
        if char not in ['(', ')']:
            return False
    return True

  2. Iterating over a string:

    Problem Statement: Write a Python function that counts the number of ‘(’ and ‘)’ characters in a string.

    1
2
3
4
5
6
7
8

    def count_parentheses(s):
    count_open, count_close = 0, 0
    for char in s:
        if char == '(':
            count_open += 1
        elif char == ')':
            count_close += 1
    return count_open, count_close

  3. Using Conditionals:

    Problem Statement: Write a Python function that checks if a string of parentheses is balanced or not.

     1
 2
 3
 4
 5
 6
 7
 8
 9
10

    def is_balanced(s):
    count = 0
    for char in s:
        if char == '(':
            count += 1
        elif char == ')':
            count -= 1
        if count < 0:
            return False
    return count == 0

  4. Working with Lists as Stacks:

    Problem Statement: Write a Python function that uses a list as a stack to check if a string of parentheses is balanced or not.

    1
2
3
4
5
6
7
8
9

    def is_balanced_stack(s):
    stack = []
    for char in s:
        if char == '(':
            stack.append(char)
        elif char == ')':
            if not stack or stack.pop() != '(':
                return False
    return not stack

  5. Indexing in Lists:

    Problem Statement: Write a Python function that takes a list of integers and returns the last item and the item at the specified index.

    1
2
3
4

    def get_items(nums, index):
    last_item = nums[-1]
    indexed_item = nums[index]
    return last_item, indexed_item

  6. Updating variables:

    Problem Statement: Write a Python function that finds the maximum number in a list of integers.

    1
2
3
4
5
6

    def find_max(nums):
    max_num = nums[0]
    for num in nums:
        if num > max_num:
            max_num = num
    return max_num

Problem Specific Drill: Using all the concepts together to solve a problem.

Problem Statement: Write a Python function that returns the length of the longest balanced parentheses in a string.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def longest_balanced(s):
    max_length = 0
    stack = [-1]
    for i in range(len(s)):
        if s[i] == '(':
            stack.append(i)
        else:
            stack.pop()
            if not stack:
                stack.append(i)
            else:
                length = i - stack[-1]
                max_length = max(max_length, length)
    return max_length