Skip to content

Longest Valid Parentheses⚓︎

Link

Description⚓︎

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

A substring is a contiguous non-empty sequence of characters within a string.

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 * 10^4
  • s[i] is '(', or ')'.

Solution⚓︎

Dynamic Programming⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int longestValidParentheses(string s) {
        if (s.empty()) return 0;

        int n = s.length();
        vector<int> dp(n);
        dp[0] = 0;
        int res = 0;

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

        return res;
    }
};
  • Time complexity: \(O(n)\);
  • Space complexity: \(O(n)\).

we start by pushing \(−1\) onto the stack. For every ( encountered, we push its index onto the stack.

For every ) encountered, we pop the topmost element. Then, the length of the currently encountered valid string of parentheses will be the difference between the current element's index and the top element of the stack.

If, while popping the element, the stack becomes empty, we will push the current element's index onto the stack. In this way, we can continue to calculate the length of the valid substrings and return the length of the longest valid string at the end.

See this example for a better understanding.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int longestValidParentheses(string s) {
        int res = 0;
        stack<int> stk;
        stk.push(-1);

        for (int i = 0; i < s.length(); i++) {
            if (s[i] == '(') {
                stk.push(i);
            } else {
                stk.pop();
                if (stk.empty()) {
                    stk.push(i);
                } else {
                    res = max(res, i - stk.top());
                }
            }
        }

        return res;
    }
};
  • Time complexity: \(O(n)\);
  • Space complexity: \(O(n)\).

Greedy⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int longestValidParentheses(string s) {
        int left = 0, right = 0, maxLength = 0;
        int n = s.length();
        if (n == 0) return 0;

        for (int i = 0; i < n; i++) {
            if (s[i] == '(') left++;
            else right++;

            if (left == right) maxLength = max(maxLength, 2 * right);
            else if (right > left) left = right = 0;
        }

        left = right = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (s[i] == '(') left++;
            else right++;

            if (left == right) maxLength = max(maxLength, 2 * left);
            else if (left > right) left = right = 0;
        }

        return maxLength;
    }
};
  • Time complexity: \(O(n)\);
  • Space complexity: \(O(1)\).