algoadvance

Leetcode 1021. Remove Outermost Parentheses

Problem Statement

You are given a valid parentheses string s (i.e., a string consisting of the characters '(' and ')' only). The string can be decomposed into multiple non-overlapping groups of non-empty balanced parentheses substrings. Your task is to remove the outermost parentheses of every primitive string and return the resulting string.

Example

Input:

s = "(()())(())"

Output:

"()()()"

Explanation:

• The input string can be decomposed into “()()”

  ”()()” .

• Removing the outer parentheses of each group results in “”.
• Therefore, the output is “()()()”.

Clarifying Questions

1. What range of length can the string s be?
   • The length of s is within the range [1, 10,000].
2. Are there always even numbers of parentheses?
   • Yes, since the input is guaranteed to be a valid parentheses string.
3. Could there be any nested but balanced parentheses groups?
   • Yes, there can be nested but balanced groups.

Strategy

1. We will use a counter to track the balance of parentheses.
2. We traverse the string and use a stack-like simulation using a counter.
3. When we encounter an opening parenthesis '(', we increment the counter. If the counter is greater than 1, it means it’s not an outermost opening parenthesis and should be added to the result.
4. When we encounter a closing parenthesis ')', we decrement the counter. If the counter is greater than 0 after decrement, it means it’s not an outermost closing parenthesis and should be added to the result.

Code

public class Solution {
    public String removeOuterParentheses(String s) {
        StringBuilder result = new StringBuilder();
        int level = 0; // This counter will act like a stack to manage nested parentheses.

        for (char c : s.toCharArray()) {
            if (c == '(') {
                // before adding, check level. It means we ignore outermost parenthesis
                if (level > 0) {
                    result.append(c);
                }
                level++;
            } else if (c == ')') {
                level--;
                // after reducing the level, check level. It means we ignore outermost parenthesis
                if (level > 0) {
                    result.append(c);
                }
            }
        }

        return result.toString();
    }

    // Main method to run the example
    public static void main(String[] args) {
        Solution sol = new Solution();
        String input = "(()())(())";
        String output = sol.removeOuterParentheses(input);
        System.out.println(output); // Output: "()()()"
    }
}

Time Complexity

• Time Complexity: O(n), where n is the length of the string s. We traverse each character in the string exactly once.
• Space Complexity: O(n), where n is the length of the string s. Although we’re using a StringBuilder to build the result, in the worst case the space used is proportional to the input size.

With this approach, we efficiently remove the outermost parentheses and return the required string while ensuring the algorithm runs efficiently in linear time.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?