101 Logo
onenoughtone

Solution Approach

Solution Overview

There are 3 main approaches to solve this problem:

  1. Stack-Based Approach - Complex approach
  2. Dynamic Programming Approach - Complex approach
  3. Two-Pass Approach - Complex approach

Approach 1: Stack-Based Approach

The stack-based approach uses a stack to keep track of the indices of unmatched parentheses. We push the index of each opening parenthesis onto the stack. When we encounter a closing parenthesis, we pop the stack if it's not empty (matching an opening parenthesis), and then calculate the length of the valid substring.

The key insight is to push -1 onto the stack initially to serve as a base for calculating the length of valid substrings.

Algorithm:

  1. Initialize an empty stack and push -1 onto it as a base for calculating lengths.
  2. Iterate through the string from left to right:
  3. a. If the current character is '(', push its index onto the stack.
  4. b. If the current character is ')':
  5. i. Pop the top element from the stack.
  6. ii. If the stack is now empty, push the current index onto the stack as a new base.
  7. iii. If the stack is not empty, calculate the length of the valid substring as (current index - top of stack).
  8. Keep track of the maximum length found.
  9. Return the maximum length.

Time Complexity:

O(n)

Where n is the length of the string. We iterate through the string once, and each character is pushed and popped from the stack at most once.

Space Complexity:

O(n)

In the worst case, the stack can contain all opening parentheses, which could be up to n/2 elements.

Approach 2: Dynamic Programming Approach

The dynamic programming approach builds up the solution by considering one character at a time. We use an array dp where dp[i] represents the length of the longest valid substring ending at index i.

The key insight is to use the previously computed values to determine the current value, considering different cases based on the current and previous characters.

Algorithm:

  1. Initialize a DP array of the same length as the input string, filled with zeros.
  2. Iterate through the string from left to right, starting from index 1:
  3. a. If the current character is ')', consider two cases:
  4. i. If the previous character is '(', we have a valid pair: dp[i] = dp[i-2] + 2.
  5. ii. If the previous character is ')' and the character at position (i - dp[i-1] - 1) is '(', we have a valid substring: dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2].
  6. Keep track of the maximum value in the DP array.
  7. Return the maximum value.

Time Complexity:

O(n)

Where n is the length of the string. We iterate through the string once, and each calculation takes constant time.

Space Complexity:

O(n)

We use a DP array of the same length as the input string.

Approach 3: Two-Pass Approach

The two-pass approach scans the string twice, once from left to right and once from right to left, using two counters to keep track of the number of opening and closing parentheses.

The key insight is that when the counters are equal, we have a valid substring, and when a counter becomes negative, we reset it to zero.

Algorithm:

  1. Initialize two counters, left and right, to zero.
  2. Scan the string from left to right:
  3. a. Increment left when encountering '(' and increment right when encountering ')'.
  4. b. If left equals right, update the maximum length.
  5. c. If right becomes greater than left, reset both counters to zero.
  6. Reset both counters to zero.
  7. Scan the string from right to left:
  8. a. Increment left when encountering '(' and increment right when encountering ')'.
  9. b. If left equals right, update the maximum length.
  10. c. If left becomes greater than right, reset both counters to zero.
  11. Return the maximum length.

Time Complexity:

O(n)

Where n is the length of the string. We scan the string twice, each scan taking O(n) time.

Space Complexity:

O(1)

We only use a constant amount of extra space regardless of the input size.

Pseudocode

solution.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function longestValidParentheses(s):
    n = length of s
    stack = empty stack
    stack.push(-1)  // Base for calculating lengths
    maxLength = 0
 
    for i from 0 to n-1:
        if s[i] == '(':
            stack.push(i)
        else:  // s[i] == ')'
            stack.pop()
            if stack is empty:
                stack.push(i)  // New base
            else:
                maxLength = max(maxLength, i - stack.top())
 
    return maxLength
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone