DDSA Solutions

1021. Remove Outermost Parentheses

EasyView on LeetCode
StringStack
Time: O(n)
Space: O(1)

Problem Overview

The string splits into primitive pieces, and each piece starts when the depth leaves 0 and ends when it comes back to 0.

Intuition

The string splits into primitive pieces, and each piece starts when the depth leaves 0 and ends when it comes back to 0. The parentheses to drop are exactly those boundary characters. An opening parenthesis is outermost when the depth is 0 just before it, and a closing parenthesis is outermost when the depth returns to 0 just after it. Everything else is copied as is, so one depth counter replaces the stack.

Algorithm

  1. 1Allocate a character buffer the size of the input and set the depth to 0.
  2. 2On an opening parenthesis, copy it if the depth is already above 0, then increase the depth.
  3. 3On a closing parenthesis, decrease the depth first, then copy it if the depth is still above 0.
  4. 4Build the answer from the filled part of the buffer.

Example Walkthrough

Input: s = "(()())(())"

  1. 1.The first piece is (()()). Its outer pair is dropped, leaving ()().
  2. 2.The second piece is (()). Its outer pair is dropped, leaving ().
  3. 3.Joining the inner parts gives ()()().

Output: "()()()"

Common Pitfalls

  • •Check the depth before increasing it for an opener, and after decreasing it for a closer. Swapping the order keeps the wrong characters.
  • •A piece like () has no inner part, so it contributes nothing.
  • •The input is valid, so the depth never goes below 0.
  • •A stack of opening parentheses only ever reports its size. A counter stores that size in constant space.
1021.cs
C#
// Approach: The stack only ever holds '(' characters, so its size is the
// whole state. Keep a depth counter instead. An opener is outermost when the
// depth is 0 before it, and a closer is outermost when the depth returns to
// 0 after it. Every other character is copied into a buffer sized to the
// input, and one string is built at the end.
// Time: O(n) Space: O(1) beyond the output

public class Solution
{
    public string RemoveOuterParentheses(string s)
    {
        char[] buf = new char[s.Length];
        int len = 0;
        int depth = 0;
        foreach (char c in s)
        {
            if (c == '(')
            {
                if (depth++ > 0)
                    buf[len++] = c;
            }
            else if (--depth > 0)
            {
                buf[len++] = c;
            }
        }

        return new string(buf, 0, len);
    }
}
Was this solution helpful?

Related Problems