Jobs

Interviews

Discussions

Reverse Substrings Between Each Pair of Parentheses

Medium

Asked by:

More companies

137 views

Topics:

StringsStacks

You are given a string s that consists of lower case English letters and brackets.

Reverse the strings in each pair of matching parentheses, starting from the innermost one.

Your result should not contain any brackets.

Example 1:

Input: s = "(abcd)"
Output: "dcba"

Example 2:

Input: s = "(u(love)i)"
Output: "iloveu"
Explanation: The substring "love" is reversed first, then the whole string is reversed.

Example 3:

Input: s = "(ed(et(oc))el)"
Output: "leetcode"
Explanation: First, we reverse the substring "oc", then "etco", and finally, the whole string.

Constraints:

1 <= s.length <= 2000
s only contains lower case English characters and parentheses.
It is guaranteed that all parentheses are balanced.

Try coding it in LeetCode

Reverse Substrings Between Each Pair of Parentheses

Medium

Asked by:

137 views

Topics:

StringsStacks

You are given a string s that consists of lower case English letters and brackets.

Reverse the strings in each pair of matching parentheses, starting from the innermost one.

Your result should not contain any brackets.

Example 1:

Input: s = "(abcd)"
Output: "dcba"

Example 2:

Input: s = "(u(love)i)"
Output: "iloveu"
Explanation: The substring "love" is reversed first, then the whole string is reversed.

Example 3:

Input: s = "(ed(et(oc))el)"
Output: "leetcode"
Explanation: First, we reverse the substring "oc", then "etco", and finally, the whole string.

Constraints:

1 <= s.length <= 2000
s only contains lower case English characters and parentheses.
It is guaranteed that all parentheses are balanced.

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 length of the input string `s`?
Can the input string `s` contain any characters other than lowercase English letters and parentheses?
If the input string `s` is empty, what should be returned?
Could you provide some example inputs and their corresponding expected outputs to clarify the expected behavior?
Is the nesting of parentheses guaranteed to be valid and balanced, or do I need to handle potentially malformed input?

Brute Force Solution

Approach

The brute force approach to reversing substrings within parentheses involves repeatedly finding the innermost set of parentheses, reversing the substring within, and removing those parentheses. We keep doing this until no parentheses remain, resulting in the final reversed string. Think of it like peeling an onion, layer by layer.

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

Find the closest pair of parentheses where there are no other parentheses nested inside.
Take the characters inside that pair of parentheses.
Reverse the order of those characters.
Replace the original parentheses and the characters inside with the reversed characters.
Repeat the process from the start: look for another innermost pair of parentheses.
Keep repeating these steps until there are no parentheses left in the string.

Code Implementation

def reverse_substrings_brute_force(input_string):
    while '(' in input_string:
        # Find the innermost parentheses
        start_index = -1
        end_index = -1
        max_start_index = -1
        for index, char in enumerate(input_string):
            if char == '(': 
                max_start_index = index
            elif char == ')':
                start_index = max_start_index
                end_index = index

                #We found the innermost pair.  Break the loop.
                break

        # Extract the substring to be reversed
        substring_to_reverse = input_string[start_index + 1:end_index]

        # Reverse the substring
        reversed_substring = substring_to_reverse[::-1]

        # Replace the parentheses and substring with the reversed substring
        input_string = input_string[:start_index] + reversed_substring + input_string[end_index + 1:]

        # Continue until no parentheses are left

    return input_string

Big(O) Analysis

Time Complexity

O(n^2) – The algorithm iterates to find the innermost parentheses. In the worst-case scenario, each iteration involves scanning the entire string of size n to find a matching pair of parentheses. Reversing the substring between the identified parentheses takes O(n) time. The process repeats until all parentheses are removed. Since each iteration removes at least one pair of parentheses and in the worst case, we may have n/2 pairs of parentheses, each iteration takes O(n) time, repeating up to O(n) times. Hence, the overall time complexity can be approximated as O(n * n), simplifying to O(n^2).

Space Complexity

O(N) – The brute force approach, as described, modifies the original string in place. However, the repeated substring reversals can be implemented using auxiliary strings or lists to hold the reversed segments before substituting them back into the original string. In the worst-case scenario, where multiple nested parentheses exist, the algorithm might need to create temporary strings or lists whose combined size could approach the length of the original string. Therefore, the space complexity is O(N), where N is the length of the input string.

Optimal Solution

Approach

The trick to efficiently reversing the substrings is to realize that the order of operations is defined by the parentheses. We can use a tool that keeps track of the 'depth' of parentheses and reverses the string at each level when we encounter the closing parenthesis.

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

Imagine you are reading the string from left to right, and you need to reverse only the parts inside the parentheses.
Use something to remember the original order of characters before encountering any opening parenthesis.
When you find an opening parenthesis, remember the current string and start building a new string for the part inside the parenthesis.
When you find a closing parenthesis, reverse the string you built up inside the parenthesis.
Now, combine the reversed string with the string you remembered from before the opening parenthesis. This forms the new string to build upon.
Repeat these steps until you have processed the whole original string. The result is the fully reversed string.

Code Implementation

def reverse_parentheses(input_string):
    stack = ['']

    for character in input_string:
        if character == '(': 
            # Start a new string for content inside parentheses.
            stack.append('')

        elif character == ')':
            # Reverse the string inside parentheses.
            reversed_substring = stack.pop()[::-1]
            stack[-1] += reversed_substring

        else:
            stack[-1] += character

    return stack[0]

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through the string of length n. Whenever a closing parenthesis is encountered, the substring within the corresponding opening parenthesis needs to be reversed. Reversing a substring can take time proportional to the length of that substring. In the worst case, if parentheses are nested deeply, the reversal operation could be applied multiple times to overlapping sections of the string. In the worst-case scenario of nested parentheses requiring multiple reversals of substrings within the larger string, the time complexity will approach O(n²), where n is the length of the string.

Space Complexity

O(N) – The algorithm uses a stack (implicitly or explicitly) to remember the current string before encountering an opening parenthesis. In the worst-case scenario, where the parentheses are deeply nested, the stack might need to store all characters of the input string before a closing parenthesis is encountered. Therefore, the maximum size of the stack can be proportional to the length of the input string, N. This leads to a space complexity of O(N).

Edge Cases

Case	How to Handle
Empty input string	Return an empty string since there's nothing to reverse.
Input string with no parentheses	Return the original string as there are no substrings to reverse.
Input string with only one set of parentheses '()'	Reverse the empty string between the parentheses, resulting in empty string which is then removed from final string.
Nested parentheses ' (a(bc)d) '	The solution should correctly handle nested parentheses by reversing from the innermost to the outermost.
Adjacent parentheses ' (ab)(cd) '	The solution should handle multiple sets of independent parentheses correctly, reversing each substring within separately.
Input string with a large number of nested parentheses to test recursion depth or stack overflow.	The solution, if recursive, should be optimized or converted to an iterative approach to handle deep nesting without stack overflow issues, or document the known limitations.
Input string with a large number of characters within parentheses to test performance.	The string reversal operation should be efficient, ideally using a StringBuilder or similar data structure to avoid excessive string concatenation.
Input string with unbalanced parentheses (invalid input).	The problem states the input will be well-formed, but handling invalid inputs gracefully with an exception or error message is good practice to prevent unexpected behavior.

Empty input string

How to Handle:

Return an empty string since there's nothing to reverse.

Input string with no parentheses

How to Handle:

Return the original string as there are no substrings to reverse.

Input string with only one set of parentheses '()'

How to Handle:

Reverse the empty string between the parentheses, resulting in empty string which is then removed from final string.

Nested parentheses ' (a(bc)d) '

How to Handle:

The solution should correctly handle nested parentheses by reversing from the innermost to the outermost.

Adjacent parentheses ' (ab)(cd) '

How to Handle:

The solution should handle multiple sets of independent parentheses correctly, reversing each substring within separately.

Input string with a large number of nested parentheses to test recursion depth or stack overflow.

How to Handle:

The solution, if recursive, should be optimized or converted to an iterative approach to handle deep nesting without stack overflow issues, or document the known limitations.

Input string with a large number of characters within parentheses to test performance.

How to Handle:

The string reversal operation should be efficient, ideally using a StringBuilder or similar data structure to avoid excessive string concatenation.

Input string with unbalanced parentheses (invalid input).

How to Handle:

The problem states the input will be well-formed, but handling invalid inputs gracefully with an exception or error message is good practice to prevent unexpected behavior.

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 length of the input string `s`?
Can the input string `s` contain any characters other than lowercase English letters and parentheses?
If the input string `s` is empty, what should be returned?
Could you provide some example inputs and their corresponding expected outputs to clarify the expected behavior?
Is the nesting of parentheses guaranteed to be valid and balanced, or do I need to handle potentially malformed input?

Brute Force Solution

Approach

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

Find the closest pair of parentheses where there are no other parentheses nested inside.
Take the characters inside that pair of parentheses.
Reverse the order of those characters.
Replace the original parentheses and the characters inside with the reversed characters.
Repeat the process from the start: look for another innermost pair of parentheses.
Keep repeating these steps until there are no parentheses left in the string.

Code Implementation

def reverse_substrings_brute_force(input_string):
    while '(' in input_string:
        # Find the innermost parentheses
        start_index = -1
        end_index = -1
        max_start_index = -1
        for index, char in enumerate(input_string):
            if char == '(': 
                max_start_index = index
            elif char == ')':
                start_index = max_start_index
                end_index = index

                #We found the innermost pair.  Break the loop.
                break

        # Extract the substring to be reversed
        substring_to_reverse = input_string[start_index + 1:end_index]

        # Reverse the substring
        reversed_substring = substring_to_reverse[::-1]

        # Replace the parentheses and substring with the reversed substring
        input_string = input_string[:start_index] + reversed_substring + input_string[end_index + 1:]

        # Continue until no parentheses are left

    return input_string

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Imagine you are reading the string from left to right, and you need to reverse only the parts inside the parentheses.
Use something to remember the original order of characters before encountering any opening parenthesis.
When you find an opening parenthesis, remember the current string and start building a new string for the part inside the parenthesis.
When you find a closing parenthesis, reverse the string you built up inside the parenthesis.
Now, combine the reversed string with the string you remembered from before the opening parenthesis. This forms the new string to build upon.
Repeat these steps until you have processed the whole original string. The result is the fully reversed string.

Code Implementation

def reverse_parentheses(input_string):
    stack = ['']

    for character in input_string:
        if character == '(': 
            # Start a new string for content inside parentheses.
            stack.append('')

        elif character == ')':
            # Reverse the string inside parentheses.
            reversed_substring = stack.pop()[::-1]
            stack[-1] += reversed_substring

        else:
            stack[-1] += character

    return stack[0]

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input string	Return an empty string since there's nothing to reverse.
Input string with no parentheses	Return the original string as there are no substrings to reverse.
Input string with only one set of parentheses '()'	Reverse the empty string between the parentheses, resulting in empty string which is then removed from final string.
Nested parentheses ' (a(bc)d) '	The solution should correctly handle nested parentheses by reversing from the innermost to the outermost.
Adjacent parentheses ' (ab)(cd) '	The solution should handle multiple sets of independent parentheses correctly, reversing each substring within separately.
Input string with a large number of nested parentheses to test recursion depth or stack overflow.	The solution, if recursive, should be optimized or converted to an iterative approach to handle deep nesting without stack overflow issues, or document the known limitations.
Input string with a large number of characters within parentheses to test performance.	The string reversal operation should be efficient, ideally using a StringBuilder or similar data structure to avoid excessive string concatenation.
Input string with unbalanced parentheses (invalid input).	The problem states the input will be well-formed, but handling invalid inputs gracefully with an exception or error message is good practice to prevent unexpected behavior.

Empty input string

How to Handle:

Return an empty string since there's nothing to reverse.

Input string with no parentheses

How to Handle:

Return the original string as there are no substrings to reverse.

Input string with only one set of parentheses '()'

How to Handle:

Reverse the empty string between the parentheses, resulting in empty string which is then removed from final string.

Nested parentheses ' (a(bc)d) '

How to Handle:

The solution should correctly handle nested parentheses by reversing from the innermost to the outermost.

Adjacent parentheses ' (ab)(cd) '

How to Handle:

The solution should handle multiple sets of independent parentheses correctly, reversing each substring within separately.

Input string with a large number of nested parentheses to test recursion depth or stack overflow.

How to Handle:

The solution, if recursive, should be optimized or converted to an iterative approach to handle deep nesting without stack overflow issues, or document the known limitations.

Input string with a large number of characters within parentheses to test performance.

How to Handle:

The string reversal operation should be efficient, ideally using a StringBuilder or similar data structure to avoid excessive string concatenation.

Input string with unbalanced parentheses (invalid input).

How to Handle:

The problem states the input will be well-formed, but handling invalid inputs gracefully with an exception or error message is good practice to prevent unexpected behavior.