# Longest Valid Parentheses
**Difficulty:** HARD
[External](https://leetcode.com/problems/longest-valid-parentheses)
Canonical: https://scaleengineer.com/dsa/problems/longest-valid-parentheses
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String, Stack
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Intuit](https://scaleengineer.com/companies/intuit), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Oracle](https://scaleengineer.com/companies/oracle), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Yahoo](https://scaleengineer.com/companies/yahoo), [Zoho](https://scaleengineer.com/companies/zoho), [eBay](https://scaleengineer.com/companies/ebay), [MakeMyTrip](https://scaleengineer.com/companies/makemytrip), [SOTI](https://scaleengineer.com/companies/soti), [Salesforce](https://scaleengineer.com/companies/salesforce), [Zeta](https://scaleengineer.com/companies/zeta), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [Sprinklr](https://scaleengineer.com/companies/sprinklr), [InMobi](https://scaleengineer.com/companies/inmobi)
---
## Problem
Given a string containing just the characters `'('` and `')'`, return _the length of the longest valid (well-formed) parentheses_ _substring_.

**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

**Constraints:**

* `0 <= s.length <= 3 * 104`
* `s[i]` is `'('`, or `')'`.

# Approaches
## Brute Force
This approach involves checking every possible substring of the given string to see if it is a valid parentheses sequence. We keep track of the length of the longest valid substring found.
**Time:** O(n^3) · **Space:** O(n)
**Pros:** Simple to understand and implement the logic.
**Cons:** Extremely inefficient with a time complexity of O(n^3).; Will result in a 'Time Limit Exceeded' error on most platforms for medium to large inputs.
### Explanation
We can generate every possible substring by using two nested loops. The outer loop fixes the starting point `i` and the inner loop fixes the ending point `j` of the substring.

For each substring, we need a helper function `isValid(substring)` to check if it's a well-formed parentheses string. This can be done using a counter. We iterate through the substring, incrementing the counter for `(` and decrementing for `)`. If the counter ever drops below zero or is not zero at the end, the substring is invalid.

The overall time complexity is high because for each of the O(n^2) substrings, we perform a check that takes up to O(n) time.

```java
class Solution {
    public boolean isValid(String s) {
        int balance = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                balance++;
            } else {
                balance--;
            }
            if (balance < 0) {
                return false;
            }
        }
        return balance == 0;
    }

    public int longestValidParentheses(String s) {
        int maxLen = 0;
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j <= s.length(); j++) {
                if (isValid(s.substring(i, j))) {
                    maxLen = Math.max(maxLen, j - i);
                }
            }
        }
        return maxLen;
    }
}
```
### Algorithm
- Initialize `maxLength` to 0.
- Iterate through the string with a start index `i` from 0 to `n-1`.
- Iterate with an end index `j` from `i+1` to `n-1`.
- Extract the substring from `i` to `j`.
- Check if the substring is a valid parentheses sequence using a helper function.
- To check for validity, use a counter. Iterate through the substring, incrementing for `(` and decrementing for `)`. If the counter ever becomes negative or is not zero at the end, it's invalid.
- If the substring is valid, update `maxLength = max(maxLength, j - i + 1)`.
- Return `maxLength` after checking all substrings.

## Dynamic Programming
A more efficient approach using dynamic programming. We build a `dp` array where `dp[i]` stores the length of the longest valid parentheses substring that *ends* at index `i`.
**Time:** O(n) · **Space:** O(n)
**Pros:** Efficient with linear time complexity.; Solves the problem for large inputs within time limits.
**Cons:** Requires O(n) extra space for the DP array.; The state transition logic can be complex to formulate correctly.
### Explanation
The core idea is to build up the solution by reusing previous results. We create a `dp` array of the same size as the input string `s`.

`dp[i]` will be non-zero only if `s[i]` is `)`. A valid substring cannot end with `(`.

If `s[i]` is `)`:
- **Case 1: `s[i-1]` is `(`**. This forms a `()` pair. The length is 2 plus the length of the valid substring ending at `i-2`. So, `dp[i] = dp[i-2] + 2`.
- **Case 2: `s[i-1]` is `)`**. This forms a `...))` structure. If the substring ending at `i-1` is valid with length `dp[i-1]`, we check the character before it, at index `i - dp[i-1] - 1`. If that character is `(`, we have found a larger valid substring. Its length is `dp[i-1] + 2` plus the length of any valid substring ending just before this new one (at `i - dp[i-1] - 2`). So, `dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2]`.

The maximum value in the `dp` array is the answer.

```java
class Solution {
    public int longestValidParentheses(String s) {
        int maxans = 0;
        int[] dp = new int[s.length()];
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                    dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                maxans = Math.max(maxans, dp[i]);
            }
        }
        return maxans;
    }
}
```
### Algorithm
- Create a `dp` array of size `n` and initialize it with zeros.
- Initialize `maxLength = 0`.
- Iterate through the string `s` from `i = 1` to `n-1`.
- If `s[i] == ')'`:
  - If `s[i-1] == '('`, it forms a `()` pair. Set `dp[i] = (i >= 2 ? dp[i-2] : 0) + 2`.
  - Else if `s[i-1] == ')'` and there's a matching `(` at `i - dp[i-1] - 1`, it forms a `(...)` structure. Set `dp[i] = dp[i-1] + (i - dp[i-1] >= 2 ? dp[i - dp[i-1] - 2] : 0) + 2`.
- Update `maxLength = max(maxLength, dp[i])` in each iteration.
- Return `maxLength`.

## Stack-Based Approach
This approach uses a stack to keep track of the indices of parentheses. When a closing parenthesis is encountered, we can determine the length of the valid substring ending at the current index by using the indices stored in the stack.
**Time:** O(n) · **Space:** O(n)
**Pros:** Efficient with linear time complexity.; Often considered more intuitive than the dynamic programming approach.
**Cons:** Requires O(n) extra space for the stack in the worst case (e.g., a string of all open parentheses).
### Explanation
The stack is used to store the indices of `(` characters. The key insight is to push a `-1` onto the stack initially. This `-1` acts as a sentinel value, representing the index just before a valid substring could start.

- When we see a `(` at index `i`, we push `i` onto the stack.
- When we see a `)` at index `i`:
  - We pop from the stack. This pop represents finding a matching `(` for the current `)`.
  - If the stack becomes empty after popping, it means the current `)` does not have a matching `(`. We then push the current index `i` onto the stack to serve as the new base for future valid substrings.
  - If the stack is not empty, the new top of the stack holds the index right before the start of the newly formed valid substring. The length of this substring is `current_index - stack.peek()`. We update our `maxLength` with this value if it's larger.

```java
import java.util.Stack;

class Solution {
    public int longestValidParentheses(String s) {
        int maxans = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.empty()) {
                    stack.push(i);
                } else {
                    maxans = Math.max(maxans, i - stack.peek());
                }
            }
        }
        return maxans;
    }
}
```
### Algorithm
- Initialize a stack and push `-1` onto it. This value acts as a sentinel.
- Initialize `maxLength = 0`.
- Iterate through the string `s` with index `i`.
- If `s[i] == '('`, push its index `i` onto the stack.
- If `s[i] == ')'`:
  - Pop from the stack.
  - If the stack is now empty, it means the current `)` is unmatched. Push the current index `i` onto the stack to act as the new base for the next potential valid substring.
  - Else (stack is not empty), the current valid substring ends at `i` and starts after the index at the top of the stack. Calculate its length `len = i - stack.peek()` and update `maxLength = max(maxLength, len)`.
- Return `maxLength`.

## Two Pointers with Two Scans
This is the most space-efficient approach. It uses two counters and scans the string twice: once from left to right, and once from right to left, to find the longest valid substring without using any extra data structures.
**Time:** O(n) · **Space:** O(1)
**Pros:** Most efficient in terms of space, using O(1) extra space.; Maintains a fast linear time complexity.
**Cons:** Requires two passes over the string.; The logic of why two passes are necessary might be less obvious at first glance.
### Explanation
This method cleverly avoids extra storage by using two counters, `left` and `right`, for open and closing parentheses, respectively.

**Left-to-Right Scan:** We iterate from the beginning of the string. We increment `left` for `(` and `right` for `)`. Whenever `left == right`, we have found a valid substring of length `2 * right`. If `right > left` at any point, it means we have an excess of closing parentheses, which makes the current substring invalid, so we reset both counters to 0.

This single scan, however, fails for cases like `(()` where there are excess open parentheses. At the end of the scan, `left` will be greater than `right`, and the valid `()` part is missed.

**Right-to-Left Scan:** To handle the cases with excess open parentheses, we perform a similar scan from the end of the string backwards. This time, if `left > right`, we reset the counters. This correctly identifies valid substrings that were missed in the first pass, like the `()` in `(()`.

The final answer is the maximum length found across both scans.

```java
class Solution {
    public int longestValidParentheses(String s) {
        int left = 0, right = 0, maxlength = 0;
        // Left to Right Scan
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                maxlength = Math.max(maxlength, 2 * right);
            } else if (right > left) {
                left = right = 0;
            }
        }
        
        left = right = 0;
        // Right to Left Scan
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                maxlength = Math.max(maxlength, 2 * left);
            } else if (left > right) {
                left = right = 0;
            }
        }
        return maxlength;
    }
}
```
### Algorithm
- Initialize `left = 0`, `right = 0`, `maxLength = 0`.
- **First Pass (Left to Right):**
  - Iterate `i` from `0` to `n-1`.
  - If `s[i] == '('`, increment `left`. Else, increment `right`.
  - If `left == right`, a valid balanced substring is found. Update `maxLength = max(maxLength, 2 * right)`.
  - If `right > left`, the sequence is broken. Reset `left = 0` and `right = 0`.
- **Second Pass (Right to Left):**
  - Reset `left = 0`, `right = 0`.
  - Iterate `i` from `n-1` down to `0`.
  - If `s[i] == '('`, increment `left`. Else, increment `right`.
  - If `left == right`, update `maxLength = max(maxLength, 2 * left)`.
  - If `left > right`, the sequence is broken (from the right). Reset `left = 0` and `right = 0`.
- Return `maxLength`.

# Solutions
### CSharp

```csharp
public class Solution {
    public int LongestValidParentheses(string s) {
        int n = s.Length;
        int[] f = new int[n + 1];
        int ans = 0;
        for (int i = 2; i <= n; ++i) {
            if (s[i - 1] == ')') {
                if (s[i - 2] == '(') {
                    f[i] = f[i - 2] + 2;
                } else {
                    int j = i - f[i - 1] - 1;
                    if (j > 0 && s[j - 1] == '(') {
                        f[i] = f[i - 1] + 2 + f[j - 1];
                    }
                }
                ans = Math.Max(ans, f[i]);
            }
        }
        return ans;
    }
}
```

### Java

```java
class Solution {
public
  int longestValidParentheses(String s) {
    int n = s.length();
    int[] f = new int[n + 1];
    int ans = 0;
    for (int i = 2; i <= n; ++i) {
      if (s.charAt(i - 1) == ')') {
        if (s.charAt(i - 2) == '(') {
          f[i] = f[i - 2] + 2;
        } else {
          int j = i - f[i - 1] - 1;
          if (j > 0 && s.charAt(j - 1) == '(') {
            f[i] = f[i - 1] + 2 + f[j - 1];
          }
        }
        ans = Math.max(ans, f[i]);
      }
    }
    return ans;
  }
}
```

### JavaScript

```javascript
/** * @param {string} s * @return {number} */ var longestValidParentheses =
  function (s) {
    const n = s.length;
    const f = new Array(n + 1).fill(0);
    for (let i = 2; i <= n; ++i) {
      if (s[i - 1] === " ) ") {
        if (s[i - 2] === " ( ") {
          f[i] = f[i - 2] + 2;
        } else {
          const j = i - f[i - 1] - 1;
          if (j && s[j - 1] === " ( ") {
            f[i] = f[i - 1] + 2 + f[j - 1];
          }
        }
      }
    }
    return Math.max(...f);
  };

```

### CPP

```cpp
class Solution {
public:
  int longestValidParentheses(string s) {
    int n = s.size();
    int f[n + 1];
    memset(f, 0, sizeof(f));
    for (int i = 2; i <= n; ++i) {
      if (s[i - 1] == ')') {
        if (s[i - 2] == '(') {
          f[i] = f[i - 2] + 2;
        } else {
          int j = i - f[i - 1] - 1;
          if (j && s[j - 1] == '(') {
            f[i] = f[i - 1] + 2 + f[j - 1];
          }
        }
      }
    }
    return *max_element(f, f + n + 1);
  }
};

```

### Python

```python
class Solution:
    def longestValidParentheses(self, s: str) -> int: left = right = 0 res = 0 for c in s:  # from left to right, '(()' => will never hit left==right if c == '(' : left += 1 else : right += 1 if left == right : res = max ( res , 2 * left ) if left < right : left = right = 0 left = right = 0 # dont forget to reset for c in reversed ( s ): # from right to left, '())' => will never hit left==right if c == '(' : left += 1 else : right += 1 if left == right : res = max ( res , 2 * left ) if left > right : # reverse '<' to '>' left = right = 0 return res ###### class Solution : def longestValidParentheses ( self , s : str ) -> int : n = len ( s ) if n < 2 : return 0 dp = [ 0 ] * n for i in range ( 1 , n ): if s [ i ] == ')' : if s [ i - 1 ] == '(' : dp [ i ] = 2 + ( dp [ i - 2 ] if i > 1 else 0 ) else : j = i - dp [ i - 1 ] - 1 if j >= 0 and s [ j ] == '(' : dp [ i ] = 2 + dp [ i - 1 ] + dp [ j - 1 ] return max ( dp ) ###### ''' >>> s="abcdefg" >>> [print(i,",",c) for i, c in enumerate(s, 1)] 1 , a 2 , b 3 , c 4 , d 5 , e 6 , f 7 , g [None, None, None, None, None, None, None] >>> ''' class Solution : def longestValidParentheses ( self , s : str ) -> int : n = len ( s ) f = [ 0 ] * ( n + 1 ) for i , c in enumerate ( s , 1 ): # starting i from 1, not 0 if c == ")" : if i > 1 and s [ i - 2 ] == "(" : f [ i ] = f [ i - 2 ] + 2 else : j = i - f [ i - 1 ] - 1 if j and s [ j - 1 ] == "(" : f [ i ] = f [ i - 1 ] + 2 + f [ j - 1 ] return max ( f )

```