Scale Engineer

Longest Valid Parentheses

Hard
#0032Time: O(n^3)Space: O(n)19 companies
Patterns
Dynamic Programming
Data structures
StringStack
Companies
AdobeAmazonBloombergIntuit

Prompt

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

4 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

O(n^3)

Space

O(n)

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem