Jobs

Interviews

Discussions

Longest Valid Parentheses

Hard

Amazon

2 views

Topics:

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

Could you describe an algorithm to solve this problem efficiently? What is the time and space complexity of your solution? Can you identify any edge cases and how your solution handles them?

Longest Valid Parentheses

Hard

Amazon

2 views

Topics:

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

Could you describe an algorithm to solve this problem efficiently? What is the time and space complexity of your solution? Can you identify any edge cases and how your solution handles them?

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:

Can the input string contain characters other than '(' and ')'?
What should I return if the input string is null or empty?
Is the input string guaranteed to be non-null?
If there are multiple valid longest substrings, can I return any one of them?
Is the maximum length of the input string limited by a certain value?

Brute Force Solution

Approach

The brute force method for finding the longest valid parentheses works by checking every single possible substring within the given string. We want to see if that substring contains a balanced arrangement of open and close parentheses. We'll keep track of the longest one we find.

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

Consider every possible section of the entire sequence of parentheses, starting from sections of length one and gradually increasing the length.
For each of those sections, check if the open and close parentheses are arranged in a correct and balanced order.
If a section is balanced, remember its length.
If a section is not balanced, forget about it and move on.
After checking all possible sections, find the longest length that you remembered. That is the length of the longest valid substring.

Code Implementation

def longest_valid_parentheses_brute_force(parentheses_string):
    max_length = 0
    string_length = len(parentheses_string)

    for start_index in range(string_length):
        for end_index in range(start_index, string_length):
            substring = parentheses_string[start_index:end_index + 1]

            # We want to check if this substring is valid
            if is_valid_parentheses(substring):

                substring_length = len(substring)
                # Keep track of the longest valid substring seen so far

                max_length = max(max_length, substring_length)

    return max_length

def is_valid_parentheses(substring):
    stack = []
    for char in substring:
        if char == '(': 
            stack.append(char)
        elif char == ')':
            if stack and stack[-1] == '(': 
                stack.pop()
            else:
                return False
    # Check that stack is empty at end to be valid
    return not stack

Big(O) Analysis

Time Complexity

O(n³) – The brute force approach iterates through all possible substrings of the input string, which has length n. The outer loops responsible for substring generation take O(n²) time because we consider substrings starting at each index and extending to every possible end index. For each substring, we then validate if the parentheses are balanced. The validation step itself requires iterating through the substring, which takes O(n) time in the worst case. Therefore, the total time complexity is O(n² * n) which simplifies to O(n³).

Space Complexity

O(1) – The brute force approach, as described, iterates through all substrings and checks each for validity. Although validity checking might use temporary variables, the plain English explanation does not explicitly mention any auxiliary data structures that scale with the input size N (length of the string). Only a constant amount of extra space is used for storing the length of the longest valid substring found so far and loop indices, which does not depend on N. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The most efficient way to find the longest valid parentheses sequence is to scan the input string twice. The first scan goes from left to right, and the second goes from right to left, both using counters to keep track of open and closed parentheses.

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

Start scanning the string from the beginning.
Keep track of the count of open parentheses and closed parentheses.
If the count of closed parentheses exceeds the count of open parentheses, reset both counts to zero.
If the counts of open and closed parentheses become equal, update the longest valid sequence seen so far with twice the value of either count.
Now, scan the string from the end to the beginning.
Again, keep track of the count of open parentheses and closed parentheses.
If the count of open parentheses exceeds the count of closed parentheses, reset both counts to zero.
If the counts of open and closed parentheses become equal, update the longest valid sequence seen so far with twice the value of either count.
After scanning in both directions, the longest valid parentheses sequence will be found.

Code Implementation

def longest_valid_parentheses(input_string):
    longest_length = 0
    open_parentheses_count = 0
    closed_parentheses_count = 0

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

        # Reset if closed exceed open
        if closed_parentheses_count > open_parentheses_count:
            open_parentheses_count = 0
            closed_parentheses_count = 0
        
        if open_parentheses_count == closed_parentheses_count:
            longest_length = max(longest_length, 2 * open_parentheses_count)

    open_parentheses_count = 0
    closed_parentheses_count = 0

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

        # Reset if open exceed closed
        if open_parentheses_count > closed_parentheses_count:
            open_parentheses_count = 0
            closed_parentheses_count = 0

        # Update when counts are equal
        if open_parentheses_count == closed_parentheses_count:
            longest_length = max(longest_length, 2 * open_parentheses_count)

    return longest_length

Big(O) Analysis

Time Complexity

O(n) – The algorithm scans the input string 's' of length 'n' twice. The first scan iterates from left to right, updating the counts of open and closed parentheses. The second scan iterates from right to left, performing similar operations. Both scans are independent and iterate through the string once; therefore, the overall time complexity is determined by the number of operations proportional to the input size 'n', resulting in O(n).

Space Complexity

O(1) – The algorithm uses two counters, one for open parentheses and one for closed parentheses. These counters are used in both the left-to-right and right-to-left scans of the input string. The amount of memory used by these counters does not depend on the length of the input string, N. Therefore, the algorithm has constant auxiliary space complexity.

Edge Cases

Case	How to Handle
Null or empty string input	Return 0, as an empty string contains no valid parentheses.
String with only one character	Return 0, as a single character cannot form a valid pair.
String with no valid parentheses (e.g., ')))')	The algorithm should correctly return 0, indicating no valid substring was found.
String with only open parentheses (e.g., '(((((')	The algorithm should correctly return 0, indicating no valid substring was found.
Maximum length string (consider memory constraints)	The algorithm needs to use O(n) space, so be mindful of potential memory limits if the input string is extremely large.
String with deeply nested valid parentheses (e.g., '((((...))))')	The stack-based or dynamic programming approach must handle potentially deep nesting without causing stack overflow or integer overflow issues during length calculation.
String with a long valid sequence at the beginning	The algorithm needs to correctly identify and track the longest valid substring and update the maximum length accordingly.
String with alternating '(' and ')' but no valid consecutive pairs (e.g., '()()()')	The algorithm must handle this by properly calculating lengths after finding valid pairs, potentially needing to consider non-contiguous valid sequences.

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:

Can the input string contain characters other than '(' and ')'?
What should I return if the input string is null or empty?
Is the input string guaranteed to be non-null?
If there are multiple valid longest substrings, can I return any one of them?
Is the maximum length of the input string limited by a certain value?

Brute Force Solution

Approach

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

Consider every possible section of the entire sequence of parentheses, starting from sections of length one and gradually increasing the length.
For each of those sections, check if the open and close parentheses are arranged in a correct and balanced order.
If a section is balanced, remember its length.
If a section is not balanced, forget about it and move on.
After checking all possible sections, find the longest length that you remembered. That is the length of the longest valid substring.

Code Implementation

def longest_valid_parentheses_brute_force(parentheses_string):
    max_length = 0
    string_length = len(parentheses_string)

    for start_index in range(string_length):
        for end_index in range(start_index, string_length):
            substring = parentheses_string[start_index:end_index + 1]

            # We want to check if this substring is valid
            if is_valid_parentheses(substring):

                substring_length = len(substring)
                # Keep track of the longest valid substring seen so far

                max_length = max(max_length, substring_length)

    return max_length

def is_valid_parentheses(substring):
    stack = []
    for char in substring:
        if char == '(': 
            stack.append(char)
        elif char == ')':
            if stack and stack[-1] == '(': 
                stack.pop()
            else:
                return False
    # Check that stack is empty at end to be valid
    return not stack

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start scanning the string from the beginning.
Keep track of the count of open parentheses and closed parentheses.
If the count of closed parentheses exceeds the count of open parentheses, reset both counts to zero.
If the counts of open and closed parentheses become equal, update the longest valid sequence seen so far with twice the value of either count.
Now, scan the string from the end to the beginning.
Again, keep track of the count of open parentheses and closed parentheses.
If the count of open parentheses exceeds the count of closed parentheses, reset both counts to zero.
If the counts of open and closed parentheses become equal, update the longest valid sequence seen so far with twice the value of either count.
After scanning in both directions, the longest valid parentheses sequence will be found.

Code Implementation

def longest_valid_parentheses(input_string):
    longest_length = 0
    open_parentheses_count = 0
    closed_parentheses_count = 0

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

        # Reset if closed exceed open
        if closed_parentheses_count > open_parentheses_count:
            open_parentheses_count = 0
            closed_parentheses_count = 0
        
        if open_parentheses_count == closed_parentheses_count:
            longest_length = max(longest_length, 2 * open_parentheses_count)

    open_parentheses_count = 0
    closed_parentheses_count = 0

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

        # Reset if open exceed closed
        if open_parentheses_count > closed_parentheses_count:
            open_parentheses_count = 0
            closed_parentheses_count = 0

        # Update when counts are equal
        if open_parentheses_count == closed_parentheses_count:
            longest_length = max(longest_length, 2 * open_parentheses_count)

    return longest_length

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty string input	Return 0, as an empty string contains no valid parentheses.
String with only one character	Return 0, as a single character cannot form a valid pair.
String with no valid parentheses (e.g., ')))')	The algorithm should correctly return 0, indicating no valid substring was found.
String with only open parentheses (e.g., '(((((')	The algorithm should correctly return 0, indicating no valid substring was found.
Maximum length string (consider memory constraints)	The algorithm needs to use O(n) space, so be mindful of potential memory limits if the input string is extremely large.
String with deeply nested valid parentheses (e.g., '((((...))))')	The stack-based or dynamic programming approach must handle potentially deep nesting without causing stack overflow or integer overflow issues during length calculation.
String with a long valid sequence at the beginning	The algorithm needs to correctly identify and track the longest valid substring and update the maximum length accordingly.
String with alternating '(' and ')' but no valid consecutive pairs (e.g., '()()()')	The algorithm must handle this by properly calculating lengths after finding valid pairs, potentially needing to consider non-contiguous valid sequences.