Longest Valid Parentheses In C,CPP,JAVA,PYTHON,C#,JS

Problem Statement: Longest Valid Parentheses

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

Definition of Valid Parentheses:

• A valid parentheses string is one that follows the rules of balanced parentheses. Each opening parenthesis '(' must have a corresponding closing parenthesis ')'.
• The string must be well-formed, meaning parentheses must be properly nested.

Input:

• A string s consisting only of characters '(' and ')'.

Output:

• The length of the longest valid parentheses substring.

Example:

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
Explanation: The string is empty, so there is no valid parentheses substring.

---

Approach:

To solve this problem, we need to find the longest substring of valid parentheses. There are several approaches to solving this problem efficiently:

1. Stack-based Approach:
   • Use a stack to keep track of the indices of opening parentheses '('.
   • Each time a closing parenthesis ')' is encountered, check if it can form a valid pair with the most recent '(' index from the stack.
   • Keep track of the length of the current valid parentheses substring.
2. Dynamic Programming (DP) Approach:
   • Use an array dp where dp[i] represents the length of the longest valid parentheses substring that ends at index i.
   • If a valid pair of parentheses is found at index i, update dp[i] accordingly by looking at previous results.
3. Two-pass Approach (Optimized Stack):
   • In one pass from left to right, and another pass from right to left, we count valid parentheses and ensure proper balancing.

---

Algorithm (Using Stack):

Stack Approach Explanation:

1. Initialization:
   • Use a stack to store the indices of the parentheses.
   • Initially, push -1 to help calculate lengths easily.
2. Traverse through the string:
   • If a '(' is encountered, push its index onto the stack.
   • If a ')' is encountered:
     • Pop the top of the stack (this removes the matching '(').
     • If the stack is empty after popping, push the current index as the base for the next potential valid substring.
     • If the stack is not empty, calculate the length of the valid parentheses substring as the difference between the current index and the index at the top of the stack.
3. Keep track of the maximum length.

---

Code Implementation (Using Stack):

Python:

def longestValidParentheses(s: str) -> int:
    stack = [-1]  # Initialize the stack with -1 to help with length calculations
    max_len = 0

    for i, char in enumerate(s):
        if char == '(':
            stack.append(i)  # Push the index of '(' onto the stack
        else:
            stack.pop()  # Pop the last element when encountering ')'
            
            if not stack:
                stack.append(i)  # Push the current index as the base for the next valid substring
            else:
                max_len = max(max_len, i - stack[-1])  # Calculate the length of valid substring

    return max_len

Explanation of Code:

• Stack initialization: We start by pushing -1 onto the stack. This helps in calculating the length of the valid parentheses substring when we encounter a valid closing parenthesis ')'.
• For each character in the string:
  • If it’s '(', we push its index onto the stack.
  • If it’s ')', we pop the stack (this removes the last '(' index). After popping, we check if the stack is empty:
    • If empty, it means the current valid substring ended, so we push the current index to help calculate future valid substrings.
    • If the stack is not empty, we compute the length of the valid substring by subtracting the index at the top of the stack from the current index.
• Tracking maximum length: As we find valid parentheses substrings, we continuously update max_len with the largest valid length found so far.

---

Time and Space Complexity:

• Time Complexity: O(n), where n is the length of the string. Each character in the string is pushed and popped from the stack at most once.
• Space Complexity: O(n), where n is the length of the string. The space complexity is dominated by the stack, which may store up to n indices in the worst case.

---

Edge Cases:

1. Empty String: If the input string is empty, the result should be 0, as there are no valid parentheses.
2. All Closing Parentheses: If the input string contains only closing parentheses, the result should be 0, since no valid parentheses can be formed.
3. All Opening Parentheses: If the input string contains only opening parentheses, the result should be 0, as no valid substring can be formed.
4. Single Pair of Valid Parentheses: A string like "()" should return 2.

---

Example Walkthrough:

Example 1:

Input: s = "(()"

• Start with an empty stack: stack = [-1].
• Traverse the string:
  • At index 0, character '(': Push 0 onto the stack. stack = [-1, 0].
  • At index 1, character '(': Push 1 onto the stack. stack = [-1, 0, 1].
  • At index 2, character ')': Pop 1 from the stack. stack = [-1, 0]. Calculate the valid substring length: 2 - 0 = 2. Update max_len = 2.
• Final result: max_len = 2.

Example 2:

Input: s = ")()())"

• Start with an empty stack: stack = [-1].
• Traverse the string:
  • At index 0, character ')': Pop -1 from the stack. stack = []. Push 0 onto the stack. stack = [0].
  • At index 1, character '(': Push 1 onto the stack. stack = [0, 1].
  • At index 2, character ')': Pop 1 from the stack. stack = [0]. Calculate the valid substring length: 2 - 0 = 2. max_len = 2.
  • At index 3, character '(': Push 3 onto the stack. stack = [0, 3].
  • At index 4, character ')': Pop 3 from the stack. stack = [0]. Calculate the valid substring length: 4 - 0 = 4. max_len = 4.
  • At index 5, character ')': Pop 0 from the stack. stack = []. Push 5 onto the stack. stack = [5].
• Final result: max_len = 4.

---

Alternative Approaches:

1. Dynamic Programming: You can use a dynamic programming array dp[i] where dp[i] represents the length of the longest valid substring ending at index i. This approach is also O(n) in time complexity but uses additional space for the dp array.
2. Two-Pass Approach: In the two-pass approach, you traverse the string from left to right to count the valid parentheses, and then you traverse from right to left to ensure that any unmatched closing parentheses are handled.

However, the stack approach provides the most intuitive and space-efficient solution for this problem.