Vultr DocsLatest Content

Longest Valid Parentheses

Updated on 09 June, 2025
Longest Valid Parentheses header image

Problem Statement

Given a string s which consists solely of the characters '(' and ')', the task is to determine the length of the longest substring where the parentheses are correctly matched and well-formed. This means that every opening parenthesis '(' has a corresponding closing parenthesis ')' and they are correctly nested according to the rules of typical parentheses sequences.

Examples

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 ')'.

Approach and Intuition

The challenge is to efficiently find the longest well-formed substring of parentheses. The solution needs to account for various cases of mismatch and nested parentheses. Here's how we can understand and approach this problem:

  1. Brute Force Checking:

    • One approach would be to generate all possible substrings of the given string and check if they are valid. However, this is impractical due to time complexity, especially considering the upper length constraint (up to 30,000).

  2. Using Stack:

    • A stack can effectively track unmatched opening parentheses.
    • Traverse the string, pushing the index of each '(' onto the stack.
    • For every ')', pop from the stack (matches the most recent '('), and calculate the length of the current valid string using the current index and the index at the top of the stack. This tells the width of the valid substring.
    • If the stack becomes empty, push the current index on the stack. This helps record the place where the last valid substring ended.

  3. Dynamic Programming:

    • Maintain a DP array where dp[i] represents the length of the longest valid substring ending at index i.
    • If s[i] is '(', set dp[i] = 0, as no valid substring can end with '('.
    • If s[i] is ')', determine if there is a '(' that matches this ')'. This is done by looking at the character before the beginning of the substring ending at dp[i-1]. If this character is '(', then the substring is valid and can be extended.

  4. Without extra space:

    • Traverse the string twice: once from left to right and once from right to left.
    • Keep track of the counts of '(' and ')' during each traversal.
    • In the left-to-right traversal, reset counters when ')' exceeds '(' since valid substrings must start afresh. Similarly, reset when '(' exceeds ')' in the right-to-left traversal.

By considering these approaches, particularly the use of a stack for linear time complexity, the solution becomes both efficient and straightforward to understand.

Solutions

  • C++
  • Java
  • C
  • JavaScript
  • Python
cpp 
class Solution {
public:
    int findMaxLen(string str) {
        int open = 0, close = 0, maxLen = 0;
        for (int index = 0; index < str.length(); index++) {
            if (str[index] == '(') {
                open++;
            } else {
                close++;
            }
            if (open == close) {
                maxLen = max(maxLen, 2 * close);
            } else if (close > open) {
                open = close = 0;
            }
        }
        open = close = 0;
        for (int index = str.length() - 1; index >= 0; index--) {
            if (str[index] == '(') {
                open++;
            } else {
                close++;
            }
            if (open == close) {
                maxLen = max(maxLen, 2 * open);
            } else if (open > close) {
                open = close = 0;
            }
        }
        return maxLen;
    }
};

The provided C++ solution focuses on finding the longest length of a well-formed parentheses substring in a given string. The problem is approached using two scans of the input string: one left-to-right and the other right-to-left. This ensures that all possible valid substrings are considered, regardless of starting and ending positions.

  • Begin by initializing two counters, open and close, to track the number of opening '(' and closing ')' parentheses respectively, and a variable maxLen to store the maximum length of valid parentheses found.
  • The first loop traverses the string from left to right:
    • Increment the open counter when encountering '(' and the close counter when encountering ')'.
    • Check if open equals close, indicating a potentially valid substring. If true, update maxLen to the maximum of its current value or twice the value of close.
    • Reset counters to zero if close exceeds open, as the substring can no longer be valid moving forward.
  • Reset the counters and run a similar loop from right to left. This time focusing on handling cases where excess opening brackets might have invalidated potential substrings during the first pass:
    • Increase open for '(' and close for ')'.
    • Update maxLen when open equals close.
    • Reset counters if open exceeds close.

By processing the string in both directions, the solution efficiently identifies the maximum length of nested and sequential valid parentheses ensuring corner cases and overlapping substrings are addressed, resulting in the longest valid parentheses string being correctly determined.

java 
public class Solution {
    public int findMaxLen(String str) {
        int open = 0, close = 0, maxlen = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '(') {
                open++;
            } else {
                close++;
            }
            if (open == close) {
                maxlen = Math.max(maxlen, 2 * close);
            } else if (close > open) {
                open = close = 0;
            }
        }
        open = close = 0;
        for (int i = str.length() - 1; i >= 0; i--) {
            if (str.charAt(i) == ')') {
                close++;
            } else {
                open++;
            }
            if (open == close) {
                maxlen = Math.max(maxlen, 2 * open);
            } else if (open > close) {
                open = close = 0;
            }
        }
        return maxlen;
    }
}

The given Java solution efficiently calculates the length of the longest valid parentheses substring. The approach utilizes a simple first pass through the string to record counts of open and close parentheses and a second pass to confirm or correct the maximal length found in the first pass.

  • Count and match parentheses opening and closing during a forward traversal. When the counts are equal, potentially update the maximum length found so far. Reset counts when the number of close parentheses exceeds the open parentheses to ensure subsequences are valid.
  • Repeat the logic in the reverse order (from the end of the string back to the start) to cover cases where an earlier close parenthesis may limit finding a longer valid substring during the forward pass.
  • Make use of two iteration variables open and close both initialized at 0 for these counts. Update the maximum length using Math.max(maxlen, 2 * [appropriate count]) during both forward and backward traverses.
  • The function returns the maximum length of valid parentheses found in the string, ensuring efficiency via two linear time complexity passes.

This method ensures accuracy by covering combinations of valid parentheses substrings from both directions and adjusts the sequence discontinuation based on imbalanced close or open parenthesis occurrences, making the solution robust and suitable for various input scenarios.

c 
int maximum(int x, int y) { return (x > y ? x : y); }
    
int maxValidParenthesesLength(char* str) {
    int open = 0, close = 0, maxLength = 0;
    for (int index = 0; index < strlen(str); index++) {
        if (str[index] == '(') {
            open++;
        } else {
            close++;
        }
        if (open == close) {
            maxLength = maximum(maxLength, 2 * close);
        } else if (close > open) {
            open = close = 0;
        }
    }
    open = close = 0;
    for (int index = strlen(str) - 1; index >= 0; index--) {
        if (str[index] == '(') {
            open++;
        } else {
            close++;
        }
        if (open == close) {
            maxLength = maximum(maxLength, 2 * open);
        } else if (open > close) {
            open = close = 0;
        }
    }
    return maxLength;
}

The provided C program defines a solution to find the length of the longest valid (properly closed and nested) parentheses substring. Follow these detailed insights into how the program accomplishes this:

  • Function Definitions & Purpose:

    • maximum(int x, int y): Helper function that returns the maximum of two integers.
    • maxValidParenthesesLength(char* str): Main function which calculates the maximum length of valid parentheses.

  • Algorithm Breakdown: The solution uses two single-pass scans of the input string str:

    1. First Pass (Left to Right):

      • Initializes two counters, open for '(' and close for ')'.
      • Iterates through the string from left to right.
      • Increments open when '(' is encountered and close for ')'.
      • When open equals close, it updates the maxLength if the current valid substring is longer than previously recorded valid substrings.
      • If close exceeds open, it resets both counters to zero since the sequence is not valid starting from the previous '('.

    2. Second Pass (Right to Left):

      • Resets the open and close counters.
      • This pass ensures the validation of sequences that might start as invalid from the beginning of the string but become valid later.
      • Proceeds similarly to the first pass but starts from the end of the string, counting and comparing as it moves towards the beginning.

  • Result Calculation:

    • After both passes, maxLength holds the length of the longest valid parentheses substring found in the input string.

This approach efficiently checks for valid sequences by considering every possible substring in two linear scans, guaranteeing the detection of the longest valid sequence of parentheses by balancing the counts in forward and reverse directions.

js 
var maxValidParenthesesLength = function (str) {
    let open = 0,
        close = 0,
        maxLen = 0;
    for (let index = 0; index < str.length; index++) {
        if (str[index] === "(") {
            open++;
        } else {
            close++;
        }
        if (open === close) {
            maxLen = Math.max(maxLen, 2 * close);
        } else if (close > open) {
            open = close = 0;
        }
    }
    open = close = 0;
    for (let index = str.length - 1; index >= 0; index--) {
        if (str[index] === "(") {
            open++;
        } else {
            close++;
        }
        if (open === close) {
            maxLen = Math.max(maxLen, 2 * open);
        } else if (open > close) {
            open = close = 0;
        }
    }
    return maxLen;
};

The JavaScript function maxValidParenthesesLength calculates the length of the longest valid (properly closed and nested) parentheses substring within a given string str. Implement a two-pass strategy ensuring a thorough scan from both left-to-right and right-to-left to account for all potential valid substrings.

  • The variables open and close track the count of '(' and ')' respectively.
  • maxLen holds the maximum length of valid parentheses found during the scans.

First, traverse the string from left to right:

  • Increment open each time a '(' is encountered and close for each ')'.
  • If open equals close, calculate the length of current valid substring as 2 * close and update maxLen if it's the longest found.
  • Reset open and close to zero if close exceeds open which indicates an unmatched ')' disrupting a valid substring.

After completing the initial pass, initialize open and close to 0 again for a reverse scan from right to left:

  • Perform similar updates to open and close but increment open for '(' and close for ')'.
  • Check conditions similar to the forward pass for valid substrings and update maxLen if necessary.
  • Reset counts when open exceeds close.

Finally, return maxLen representing the length of the longest valid parentheses substring determined after both passes. This ensures the function handles all variations and combinations by considering disruptions caused by unmatched parentheses from either end of the string.

python 
class Solution:
    def findLongestValid(self, sequence: str) -> int:
        open_bracket, close_bracket, max_length = 0, 0, 0
        for char in sequence:
            if char == "(":
                open_bracket += 1
            else:
                close_bracket += 1
            if open_bracket == close_bracket:
                max_length = max(max_length, 2 * close_bracket)
            elif close_bracket > open_bracket:
                open_bracket = close_bracket = 0
        open_bracket = close_bracket = 0
        for index in range(len(sequence) - 1, -1, -1):
            if sequence[index] == "(":
                open_bracket += 1
            else:
                close_bracket += 1
            if open_bracket == close_bracket:
                max_length = max(max_length, 2 * open_bracket)
            elif open_bracket > close_bracket:
                open_bracket = close_bracket = 0
        return max_length

The Python code implements a solution to find the length of the longest valid parentheses substring within a given string. The approach involves two scans of the string:

  1. The first scan moves from left to right:

    • Initialize counters for open and close brackets (open_bracket, close_bracket) and a variable to store the maximum length of valid parentheses (max_length).
    • Increment open_bracket for every '(' found, and close_bracket for every ')'.
    • Whenever open_bracket equals close_bracket, calculate potential max length as 2 * close_bracket and update max_length if this is greater.
    • If close_bracket exceeds open_bracket at any point, reset both counters to zero since it's impossible to have a valid substring starting before this point.

  2. The second scan moves from right to left:

    • Reinitialize the open_bracket and close_bracket counters to zero.
    • This time, increment open_bracket for every '(' encountered and close_bracket for every ')'.
    • Match occurs when open_bracket equals close_bracket, whereby the potential valid substring's length is computed as 2 * open_bracket.
    • Adjust the maximum length if this new calculated length exceeds the previously recorded max_length.
    • Reset counters to zero if open_bracket exceeds close_bracket, indicating invalid starting points for a substring.

The function finally returns max_length as the length of the longest valid parentheses substring found during the scans. This dual-scan technique efficiently checks valid substrings by considering balances from both ends of the sequence, ensuring all potential valid sequences are accounted for.

Comments