Longest Valid Parentheses

HARD

Description

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

Approaches

Checkout 4 different approaches to solve Longest Valid Parentheses. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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.

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;
    }
}

Complexity Analysis

Time Complexity: O(n^3)Space Complexity: O(n)

Pros and Cons

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.

Code Solutions

Checking out 5 solutions in different languages for Longest Valid Parentheses. Click on different languages to view the code.

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;
    }
}

Video Solution

Watch the video walkthrough for Longest Valid Parentheses

Patterns:

Dynamic Programming

Data Structures:

StringStack

Companies:

Adobe |Amazon |Bloomberg |Intuit |