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:
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.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.
 If the stack is not empty after the pop, update
Return the Result: Return the value of
max_length
.
Here’s the code:


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.


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 welloptimized dynamic programming solution for an efficient resolution.
“Longest Valid Parentheses” focuses on the maximal length of a wellformed 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:
“Valid Parentheses” (LeetCode Problem #20): This is a simpler version of the problem where you just need to validate if the parentheses are balanced.
“Min Stack” (LeetCode Problem #155): This problem will help you understand how to use a stack to keep track of the minimum element.
“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.
“Implement Queue using Stacks” (LeetCode Problem #232): This problem gives practice on manipulating stacks.
“Decode String” (LeetCode Problem #394): This problem involves a similar concept of parsing a string and making use of a stack.
“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.
“Climbing Stairs” (LeetCode Problem #70): This problem introduces the concept of dynamic programming, a key concept for the problem at hand.
“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.”
“Balanced Binary Tree” (LeetCode Problem #110): The idea of a balanced tree is conceptually similar to the idea of balanced parentheses.
“Longest Increasing Subsequence” (LeetCode Problem #300): This problem introduces a more advanced form of dynamic programming which is useful for the problem at hand.


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 problemsolving approach involves using a stack to track indices of parentheses while checking the validness of the parentheses substring.
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.
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).
Iterating over a string: The solution involves iterating over the string and performing certain actions based on the current character.
Using Conditionals: Based on the character in the string (whether it’s an opening or closing parenthesis), different actions are performed. Understanding ifelse conditional statements is key here.
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).
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:
 Understanding of Strings
 Iterating over a string
 Using Conditionals
 Working with Lists as Stacks
 Indexing in Lists
 Updating variables
Problemsolving 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).
The algorithm starts by iterating through the string, one character at a time.
If the current character is an opening parenthesis, it’s index is added to the stack.
If the current character is a closing parenthesis, the top element (index) is popped from the stack, indicating that a pair has been completed.
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.
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 updatesmax_length
.The algorithm repeats steps 25 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
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
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
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
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
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
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.

