Jobs

Interviews

Discussions

Remove Outermost Parentheses

Easy

Apple

2 views

Topics:

StringsStacks

A valid parentheses string is either empty "", "(" + A + ")", or A + B, where A and B are valid parentheses strings, and + represents string concatenation. For example, "", "()", "(())()", and "(()(()))" are all valid parentheses strings.

A valid parentheses string s is primitive if it is nonempty, and there does not exist a way to split it into s = A + B, with A and B nonempty valid parentheses strings.

Given a valid parentheses string s, consider its primitive decomposition: s = P1 + P2 + ... + Pk, where Pi are primitive valid parentheses strings.

Return s after removing the outermost parentheses of every primitive string in the primitive decomposition of s.

Example 1:

Input: s = "(()())(())" Output: "()()()" Explanation: The input string is `"(()())(())

Remove Outermost Parentheses

Easy

Apple

2 views

Topics:

StringsStacks

A valid parentheses string s is primitive if it is nonempty, and there does not exist a way to split it into s = A + B, with A and B nonempty valid parentheses strings.

Given a valid parentheses string s, consider its primitive decomposition: s = P1 + P2 + ... + Pk, where Pi are primitive valid parentheses strings.

Return s after removing the outermost parentheses of every primitive string in the primitive decomposition of s.

Example 1:

Input: s = "(()())(())" Output: "()()()" Explanation: The input string is `"(()())(())

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 `S` contain characters other than '(' and ')'?
Is an empty string a valid input, and if so, what should the output be?
Is the input string `S` guaranteed to be a valid parentheses string, meaning that at any point we will never have more ')' than '('?
By 'outermost parentheses' are we referring to the matching pair that encloses the entire string or any outermost pair, even within nested structures?
What should the output be if the input string doesn't contain any primitive decomposition at all, i.e., consists of a single primitive string?

Brute Force Solution

Approach

The brute force approach involves examining every possible way to remove matching outer parentheses from the given string. We try removing different combinations of outermost pairs and see what is left. We continue this process until we find the simplest result.

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

Start with the entire string of parentheses.
Try removing one matching pair of outermost parentheses and keep what's left.
Then, try removing a different single pair of outermost parentheses (if there's more than one way to remove a single pair initially) and keep what's left.
Repeat this process by removing two pairs, then three pairs, and so on until you have removed all possible matching outer parentheses pairs in every possible way.
After trying all removal possibilities, compare the results to find the shortest result. This shortest result is the answer.

Code Implementation

def remove_outermost_parentheses_brute_force(parentheses_string):
    shortest_result = parentheses_string

    # Iterate through all possible numbers of pairs to remove
    for num_pairs_to_remove in range(len(parentheses_string) // 2 + 1):
        possible_results = generate_results(
            parentheses_string, num_pairs_to_remove
        )

        # Find the shortest result among current possibilities
        for current_result in possible_results:
            if len(current_result) < len(shortest_result):
                shortest_result = current_result

    return shortest_result

def generate_results(parentheses_string, num_pairs_to_remove):
    results = []
    generate_combinations(
        parentheses_string, num_pairs_to_remove, results, ""
    )
    return results

def generate_combinations(
    parentheses_string, num_pairs_to_remove, results, current_combination
):
    if num_pairs_to_remove == 0:

        # No more pairs to remove, add remainder
        results.append(current_combination + parentheses_string)
        return

    if not parentheses_string:
        return

    open_index = -1
    close_index = -1
    balance = 0

    # Find matching outermost parentheses
    for index, char in enumerate(parentheses_string):
        if char == '(': 
            balance += 1
            if open_index == -1:
                open_index = index
        elif char == ')':
            balance -= 1
            if balance == 0:
                close_index = index
                break

    if open_index != -1 and close_index != -1:

        # Remove outermost parentheses pair
        remaining_string = (
            parentheses_string[:open_index]
            + parentheses_string[open_index + 1 : close_index]
            + parentheses_string[close_index + 1 :]
        )
        generate_combinations(
            remaining_string,
            num_pairs_to_remove - 1,
            results,
            current_combination,
        )

    else:

        # No matching parentheses, add the original string
        results.append(current_combination + parentheses_string)

Big(O) Analysis

Time Complexity

O(2^n) – The described brute force approach explores all possible combinations of removing outermost parentheses pairs. In the worst case, where all parentheses can potentially be removed in various combinations, the algorithm effectively considers every possible subset of matching parenthesis pairs. Since there can be potentially n/2 matching pairs, this results in checking on the order of 2^(n/2) possibilities. Because 2^(n/2) is equivalent to 2^n, the time complexity is O(2^n).

Space Complexity

O(N^2) – The described brute force approach involves generating substrings by removing different combinations of outer parentheses. In the worst case, we might generate all possible substrings of the input string to find the shortest valid one. Storing all these substrings would require space proportional to the number of possible substrings. A string of length N can have O(N^2) substrings, as each substring is determined by two indices, and there are N choices for each index, leading to N*N = N^2 combinations. Therefore, the auxiliary space used to store these substrings in the worst case is O(N^2).

Optimal Solution

Approach

The goal is to remove the outermost matching parentheses from groups within a larger string of parentheses. We keep track of the balance between open and close parentheses to know when a group starts and ends. We only add parentheses that are *not* the outermost ones.

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

Start with a counter set to zero, which represents how many open parentheses we've seen without a matching closing one.
Go through the string of parentheses, one character at a time.
If you see an open parenthesis, and the counter is already greater than zero (meaning it's not the first open parenthesis in a primitive string), then add it to the result.
Increase the counter every time you see an open parenthesis.
If you see a closing parenthesis, first decrease the counter.
If the counter is still greater than zero after decreasing it (meaning it's not the last closing parenthesis in a primitive string), then add the closing parenthesis to the result.
Continue this process until you've gone through the entire string.

Code Implementation

def remove_outer_parentheses(parentheses_string):
    open_parentheses_count = 0
    result_string = ""

    for character in parentheses_string:
        if character == '(': 
            # Add to result only if it's not the outermost opening parenthesis.
            if open_parentheses_count > 0:
                result_string += character

            open_parentheses_count += 1

        elif character == ')':
            open_parentheses_count -= 1

            # Add to result only if it's not the outermost closing parenthesis.
            if open_parentheses_count > 0:
                result_string += character

    return result_string

Big(O) Analysis

Time Complexity

O(n) – The solution iterates through the input string of parentheses once. For each character, it performs a constant number of operations: incrementing or decrementing a counter, comparing the counter to zero, and potentially appending the character to a result string. The number of operations is directly proportional to the length of the input string, denoted as n. Therefore, the time complexity is O(n).

Space Complexity

O(N) – The algorithm uses a result string to store the parentheses that are not outermost. In the worst-case scenario, nearly all parentheses except the very first opening and last closing parentheses from the outermost primitive strings are added to the result. Thus, the result string's length could grow linearly with the input string's length, N, where N is the number of characters (parentheses) in the input string. Therefore, the auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Empty string input	Return an empty string immediately since there are no parentheses to process.
Input string with no parentheses	Return the original string as there's nothing to remove.
Input string with only one pair of parentheses	Return an empty string after removing the only outermost pair.
Nested parentheses with multiple layers of nesting	The counter-based approach correctly handles the depth and identifies outermost parentheses for removal.
Unbalanced parentheses (more opening than closing or vice-versa)	The counter will not return to 0, leaving the unbalanced parentheses in the result.
String with multiple primitive valid parentheses strings concatenated	The algorithm correctly identifies and removes the outermost parentheses of each primitive string.
Input string containing characters other than '(' and ')'	The algorithm only considers parentheses, effectively ignoring other characters.
Maximum string length to prevent excessive memory usage	Implement a check at the start to reject strings exceeding a predefined maximum length.

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 `S` contain characters other than '(' and ')'?
Is an empty string a valid input, and if so, what should the output be?
Is the input string `S` guaranteed to be a valid parentheses string, meaning that at any point we will never have more ')' than '('?
By 'outermost parentheses' are we referring to the matching pair that encloses the entire string or any outermost pair, even within nested structures?
What should the output be if the input string doesn't contain any primitive decomposition at all, i.e., consists of a single primitive string?

Brute Force Solution

Approach

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

Start with the entire string of parentheses.
Try removing one matching pair of outermost parentheses and keep what's left.
Then, try removing a different single pair of outermost parentheses (if there's more than one way to remove a single pair initially) and keep what's left.
Repeat this process by removing two pairs, then three pairs, and so on until you have removed all possible matching outer parentheses pairs in every possible way.
After trying all removal possibilities, compare the results to find the shortest result. This shortest result is the answer.

Code Implementation

def remove_outermost_parentheses_brute_force(parentheses_string):
    shortest_result = parentheses_string

    # Iterate through all possible numbers of pairs to remove
    for num_pairs_to_remove in range(len(parentheses_string) // 2 + 1):
        possible_results = generate_results(
            parentheses_string, num_pairs_to_remove
        )

        # Find the shortest result among current possibilities
        for current_result in possible_results:
            if len(current_result) < len(shortest_result):
                shortest_result = current_result

    return shortest_result

def generate_results(parentheses_string, num_pairs_to_remove):
    results = []
    generate_combinations(
        parentheses_string, num_pairs_to_remove, results, ""
    )
    return results

def generate_combinations(
    parentheses_string, num_pairs_to_remove, results, current_combination
):
    if num_pairs_to_remove == 0:

        # No more pairs to remove, add remainder
        results.append(current_combination + parentheses_string)
        return

    if not parentheses_string:
        return

    open_index = -1
    close_index = -1
    balance = 0

    # Find matching outermost parentheses
    for index, char in enumerate(parentheses_string):
        if char == '(': 
            balance += 1
            if open_index == -1:
                open_index = index
        elif char == ')':
            balance -= 1
            if balance == 0:
                close_index = index
                break

    if open_index != -1 and close_index != -1:

        # Remove outermost parentheses pair
        remaining_string = (
            parentheses_string[:open_index]
            + parentheses_string[open_index + 1 : close_index]
            + parentheses_string[close_index + 1 :]
        )
        generate_combinations(
            remaining_string,
            num_pairs_to_remove - 1,
            results,
            current_combination,
        )

    else:

        # No matching parentheses, add the original string
        results.append(current_combination + parentheses_string)

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start with a counter set to zero, which represents how many open parentheses we've seen without a matching closing one.
Go through the string of parentheses, one character at a time.
If you see an open parenthesis, and the counter is already greater than zero (meaning it's not the first open parenthesis in a primitive string), then add it to the result.
Increase the counter every time you see an open parenthesis.
If you see a closing parenthesis, first decrease the counter.
If the counter is still greater than zero after decreasing it (meaning it's not the last closing parenthesis in a primitive string), then add the closing parenthesis to the result.
Continue this process until you've gone through the entire string.

Code Implementation

def remove_outer_parentheses(parentheses_string):
    open_parentheses_count = 0
    result_string = ""

    for character in parentheses_string:
        if character == '(': 
            # Add to result only if it's not the outermost opening parenthesis.
            if open_parentheses_count > 0:
                result_string += character

            open_parentheses_count += 1

        elif character == ')':
            open_parentheses_count -= 1

            # Add to result only if it's not the outermost closing parenthesis.
            if open_parentheses_count > 0:
                result_string += character

    return result_string

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty string input	Return an empty string immediately since there are no parentheses to process.
Input string with no parentheses	Return the original string as there's nothing to remove.
Input string with only one pair of parentheses	Return an empty string after removing the only outermost pair.
Nested parentheses with multiple layers of nesting	The counter-based approach correctly handles the depth and identifies outermost parentheses for removal.
Unbalanced parentheses (more opening than closing or vice-versa)	The counter will not return to 0, leaving the unbalanced parentheses in the result.
String with multiple primitive valid parentheses strings concatenated	The algorithm correctly identifies and removes the outermost parentheses of each primitive string.
Input string containing characters other than '(' and ')'	The algorithm only considers parentheses, effectively ignoring other characters.
Maximum string length to prevent excessive memory usage	Implement a check at the start to reject strings exceeding a predefined maximum length.