Longest Valid Parentheses

---

Longest Valid Parentheses: 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 2:

Input: s = ""
Output: 0

---

Constraints:

• 0 <= s.length <= 3 * 10^4
• s[i] is '(', or ')'.

---

Try this Problem on your own or check similar problems:

1. Valid Parentheses

Solution:

Java

public int longestValidParentheses(String s) {
    int n = s.length();
    if(n <= 1) return 0;

    int maxLength = 0;
    int[] dp = new int[n];

    for(int i = 0; i < n; ++i){
        if(s.charAt(i) == ')' && i > 0){
            int matchingIdx = i - dp[i - 1] - 1;
            if(matchingIdx >= 0 && s.charAt(matchingIdx) == '('){
                dp[i] = dp[i - 1] + 2;
                if(matchingIdx > 0){
                    dp[i] += dp[matchingIdx - 1];
                }
                maxLength = Math.max(maxLength, dp[i]);
            }
        }
    }

    return maxLength;
}

JavaScript

/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function (s) {
  const n = s.length;
  if (n <= 1) return 0;

  let maxLength = 0;
  const dp = new Array(n).fill(0);

  for (let i = 0; i < n; ++i) {
    if (s[i] === ")" && i > 0) {
      const matchingIdx = i - dp[i - 1] - 1;
      if (matchingIdx >= 0 && s[matchingIdx] === "(") {
        dp[i] = dp[i - 1] + 2;
        if (matchingIdx > 0) {
          dp[i] += dp[matchingIdx - 1];
        }
        maxLength = Math.max(maxLength, dp[i]);
      }
    }
  }

  return maxLength;
};

Python

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        n = len(s)
        if n <= 1:
            return 0

        maxLength = 0
        dp = [0] * n

        for i in range(n):
            if s[i] == ')' and i > 0:
                matchingIdx = i - dp[i - 1] - 1
                if matchingIdx >= 0 and s[matchingIdx] == '(':
                    dp[i] = dp[i - 1] + 2
                    if matchingIdx > 0:
                        dp[i] += dp[matchingIdx - 1]
                    maxLength = max(maxLength, dp[i])

        return maxLength

C++

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.length();
        if (n <= 1)
            return 0;

        int maxLength = 0;
        std::vector<int> dp(n, 0);

        for (int i = 0; i < n; ++i) {
            if (s[i] == ')' && i > 0) {
                int matchingIdx = i - dp[i - 1] - 1;
                if (matchingIdx >= 0 && s[matchingIdx] == '(') {
                    dp[i] = dp[i - 1] + 2;
                    if (matchingIdx > 0) {
                        dp[i] += dp[matchingIdx - 1];
                    }
                    maxLength = std::max(maxLength, dp[i]);
                }
            }
        }

        return maxLength;
    }
};

---

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(n)

---

Explanation:

We traverse the string only once and we store the max length for each index in dp array leading to linear time and space complexity proportional to the length of input string. The problem can be solved by using Dynamic programming approach, for each index we check if the character at it is a closing bracket, and we try to find the opening bracket we have already traversed over. To find the opening brackets we can use the dp array, since it holds the length of valid parentheses substring for the previous index, so for example if we have (()) and we're at index = 3 the last ), we know that dp[index-1]=2 since we have the middle pair of ( and ). So to find the opening we subtract the length of the longest brackets so far from the current index and we offset it by 1 (3 - 2 - 1 = 0), we check if the index is valid and if the brackets at it is (, if it is we know the maximum valid substring length will be that of the previous one plus two additional brackets. Also we check if there has been any other group of valid brackets pairs before our start (, for example (()) (()), we can easily check that by using the dp for the index just before our first (. For each index we check if can update the maxLength which is later returned as final result.