Jobs

Interviews

Discussions

Longest Valid Parentheses

Hard

Nike

2 views

Topics:

StringsStacksDynamic Programming

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

Try coding it in LeetCode

Longest Valid Parentheses

Hard

Nike

2 views

Topics:

StringsStacksDynamic Programming

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum possible length of the input string s?
If the input string is empty or contains no valid parentheses, what value should I return?
Does the input string contain only '(' and ')' characters, or might it contain other characters as well?
Could you provide an example of a long input string to illustrate the expected behavior?
Are we looking for a contiguous substring only, or can the parentheses be non-contiguous?

Brute Force Solution

Approach

The brute force way to find the longest valid parentheses sequence is to check every possible sequence of parentheses within the string. We're basically trying every starting point and every possible length to see if that section of the parentheses string is 'valid'. By checking every possible substring, we are guaranteed to find the longest valid one.

Here's how the algorithm would work step-by-step:

Consider all possible substrings within the given parentheses string.
For each substring, check if it is a 'valid' parentheses sequence. A valid sequence means that for every opening parenthesis, there is a matching closing parenthesis in the correct order.
Keep track of the length of each valid parentheses sequence you find.
After checking all possible substrings, choose the longest valid parentheses sequence that you found. Its length is the answer.

Code Implementation

def longest_valid_parentheses_brute_force(parentheses_string):
    max_length = 0

    # Consider all possible substrings
    for start_index in range(len(parentheses_string)):
        for end_index in range(start_index, len(parentheses_string)):
            substring = parentheses_string[start_index:end_index + 1]

            # Check if the current substring is valid
            if is_valid_parentheses(substring):
                max_length = max(max_length, len(substring))

    return max_length

def is_valid_parentheses(substring):
    stack = []

    # Iterate through each character in the substring
    for character in substring:
        if character == '(': 
            stack.append(character)

        elif character == ')':
            # If the stack is empty, then it is invalid
            if not stack:
                return False

            stack.pop()

    # A valid string means all open parentheses have been closed
    return not stack

Big(O) Analysis

Time Complexity

O(n^3) – The provided solution iterates through all possible substrings of the input string of length n. Generating all substrings requires two nested loops, resulting in O(n^2) substrings. For each substring, the solution checks its validity as a parentheses sequence. This validity check involves iterating through the substring (in the worst case, the entire substring), which takes O(n) time. Therefore, the overall time complexity is O(n^2) * O(n) = O(n^3).

Space Complexity

O(1) – The brute force approach, as described, iterates through all possible substrings but doesn't explicitly create any auxiliary data structures that scale with the input string's length (N). Although the algorithm implicitly keeps track of the length of the longest valid sequence found so far, this requires only a single integer variable. Similarly, checking if a substring is 'valid' might involve temporary variables, but these are constant in number and do not depend on N. Therefore, the space complexity remains constant.

Optimal Solution

Approach

The efficient way to find the longest valid set of parentheses is to scan the input twice, once from left to right and once from right to left. We use counters to keep track of open and closed parentheses and reset these counters when they become unbalanced.

Here's how the algorithm would work step-by-step:

First, we'll go through the string of parentheses from the start to the end.
We'll use two numbers: one to count how many open parentheses we've seen, and another to count the closed ones.
As we go, if the numbers are ever the same, it means we've found a valid sequence of parentheses. We remember the length of this sequence.
If we ever find more closed parentheses than open ones, it means the sequence is broken, so we reset both counters to zero and keep going.
Next, we do the exact same thing, but this time we go through the string from the end to the start.
This time, we reset the counters when we see more open parentheses than closed ones.
By going both ways, we are sure to find the longest valid sequence, handling cases where there might be an imbalance at either the beginning or the end of the string.

Code Implementation

def longest_valid_parentheses(s):
    max_length = 0
    open_parentheses_count = 0
    closed_parentheses_count = 0

    # Scan from left to right.
    for character in s:
        if character == '(': 
            open_parentheses_count += 1
        else:
            closed_parentheses_count += 1

        if open_parentheses_count == closed_parentheses_count:
            max_length = max(max_length, 2 * open_parentheses_count)
        elif closed_parentheses_count > open_parentheses_count:
            # Reset counts when unbalanced.
            open_parentheses_count = 0
            closed_parentheses_count = 0

    open_parentheses_count = 0
    closed_parentheses_count = 0

    # Scan from right to left.
    for character in reversed(s):
        if character == '(': 
            open_parentheses_count += 1
        else:
            closed_parentheses_count += 1

        if open_parentheses_count == closed_parentheses_count:
            max_length = max(max_length, 2 * open_parentheses_count)
        elif open_parentheses_count > closed_parentheses_count:
            # Reset counts when unbalanced.
            open_parentheses_count = 0
            closed_parentheses_count = 0

    return max_length

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string of length n twice: once from left to right and once from right to left. Each iteration involves incrementing counters and comparing them, which are constant-time operations. Because the dominant factor is the number of iterations directly proportional to the input size, the time complexity is O(n).

Space Complexity

O(1) – The algorithm uses two counters, one for open parentheses and one for closed parentheses. These counters are updated iteratively during the two scans of the input string. Since the number of counters remains constant (two variables) regardless of the input string's length N, the space complexity is constant.

Edge Cases

Case	How to Handle
Empty string input	Return 0 as there are no parentheses to validate.
String with only one character	Return 0 as a single parenthesis is never valid.
String with only open parentheses '((('	Return 0 as there are no closing parentheses to form a valid substring.
String with only closed parentheses ')))'	Return 0 as there are no open parentheses to form a valid substring.
String with a perfectly balanced parentheses '()()'	The algorithm should correctly identify and return the total length of the string.
String with nested and balanced parentheses '(()())'	The algorithm should correctly identify and return the total length of the string.
String with unbalanced parentheses at the beginning ')(()))'	The algorithm should identify the longest valid substring, '()))', and return its length, which is 4.
Maximum string length allowed by the platform with complex unbalanced structure	Ensure the solution has O(n) time complexity using dynamic programming or stack to avoid exceeding time limit or memory limit.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum possible length of the input string s?
If the input string is empty or contains no valid parentheses, what value should I return?
Does the input string contain only '(' and ')' characters, or might it contain other characters as well?
Could you provide an example of a long input string to illustrate the expected behavior?
Are we looking for a contiguous substring only, or can the parentheses be non-contiguous?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Consider all possible substrings within the given parentheses string.
For each substring, check if it is a 'valid' parentheses sequence. A valid sequence means that for every opening parenthesis, there is a matching closing parenthesis in the correct order.
Keep track of the length of each valid parentheses sequence you find.
After checking all possible substrings, choose the longest valid parentheses sequence that you found. Its length is the answer.

Code Implementation

def longest_valid_parentheses_brute_force(parentheses_string):
    max_length = 0

    # Consider all possible substrings
    for start_index in range(len(parentheses_string)):
        for end_index in range(start_index, len(parentheses_string)):
            substring = parentheses_string[start_index:end_index + 1]

            # Check if the current substring is valid
            if is_valid_parentheses(substring):
                max_length = max(max_length, len(substring))

    return max_length

def is_valid_parentheses(substring):
    stack = []

    # Iterate through each character in the substring
    for character in substring:
        if character == '(': 
            stack.append(character)

        elif character == ')':
            # If the stack is empty, then it is invalid
            if not stack:
                return False

            stack.pop()

    # A valid string means all open parentheses have been closed
    return not stack

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, we'll go through the string of parentheses from the start to the end.
We'll use two numbers: one to count how many open parentheses we've seen, and another to count the closed ones.
As we go, if the numbers are ever the same, it means we've found a valid sequence of parentheses. We remember the length of this sequence.
If we ever find more closed parentheses than open ones, it means the sequence is broken, so we reset both counters to zero and keep going.
Next, we do the exact same thing, but this time we go through the string from the end to the start.
This time, we reset the counters when we see more open parentheses than closed ones.
By going both ways, we are sure to find the longest valid sequence, handling cases where there might be an imbalance at either the beginning or the end of the string.

Code Implementation

def longest_valid_parentheses(s):
    max_length = 0
    open_parentheses_count = 0
    closed_parentheses_count = 0

    # Scan from left to right.
    for character in s:
        if character == '(': 
            open_parentheses_count += 1
        else:
            closed_parentheses_count += 1

        if open_parentheses_count == closed_parentheses_count:
            max_length = max(max_length, 2 * open_parentheses_count)
        elif closed_parentheses_count > open_parentheses_count:
            # Reset counts when unbalanced.
            open_parentheses_count = 0
            closed_parentheses_count = 0

    open_parentheses_count = 0
    closed_parentheses_count = 0

    # Scan from right to left.
    for character in reversed(s):
        if character == '(': 
            open_parentheses_count += 1
        else:
            closed_parentheses_count += 1

        if open_parentheses_count == closed_parentheses_count:
            max_length = max(max_length, 2 * open_parentheses_count)
        elif open_parentheses_count > closed_parentheses_count:
            # Reset counts when unbalanced.
            open_parentheses_count = 0
            closed_parentheses_count = 0

    return max_length

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty string input	Return 0 as there are no parentheses to validate.
String with only one character	Return 0 as a single parenthesis is never valid.
String with only open parentheses '((('	Return 0 as there are no closing parentheses to form a valid substring.
String with only closed parentheses ')))'	Return 0 as there are no open parentheses to form a valid substring.
String with a perfectly balanced parentheses '()()'	The algorithm should correctly identify and return the total length of the string.
String with nested and balanced parentheses '(()())'	The algorithm should correctly identify and return the total length of the string.
String with unbalanced parentheses at the beginning ')(()))'	The algorithm should identify the longest valid substring, '()))', and return its length, which is 4.
Maximum string length allowed by the platform with complex unbalanced structure	Ensure the solution has O(n) time complexity using dynamic programming or stack to avoid exceeding time limit or memory limit.