A valid parentheses string is either empty "", "(" + A + ")", or A + B, where A and B are valid parentheses strings, and + represents string concatenation.
"", "()", "(())()", 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 "(()())(())", with primitive decomposition "(()())" + "(())". After removing outer parentheses of each part, this is "()()" + "()" = "()()()".
Example 2:
Input: s = "(()())(())(()(()))" Output: "()()()()(())" Explanation: The input string is "(()())(())(()(()))", with primitive decomposition "(()())" + "(())" + "(()(()))". After removing outer parentheses of each part, this is "()()" + "()" + "()(())" = "()()()()(())".
Example 3:
Input: s = "()()" Output: "" Explanation: The input string is "()()", with primitive decomposition "()" + "()". After removing outer parentheses of each part, this is "" + "" = "".
Constraints:
1 <= s.length <= 105s[i] is either '(' or ')'.s is a valid parentheses string.Problem Overview: You are given a valid parentheses string s. The string can be split into multiple primitive valid parentheses substrings. The task is to remove the outermost pair of parentheses from every primitive part and return the final combined string.
Approach 1: Using a Counter to Track Depth (O(n) time, O(1) space)
This approach tracks the current nesting depth while iterating through the string once. Increment the depth when encountering '(' and decrement it when encountering ')'. The key insight: characters should only be added to the result when they are not the outermost parentheses. For an opening bracket, append it only if the current depth is already greater than zero before incrementing. For a closing bracket, decrement first and append only if the depth remains greater than zero. This effectively strips the first and last parentheses of each primitive group without explicitly splitting the string. Since the algorithm performs a single pass and only maintains an integer counter, it runs in O(n) time with O(1) extra space. This method is the most common solution when working with string traversal problems involving balanced parentheses.
Approach 2: Stack-Based Iteration (O(n) time, O(n) space)
A more explicit method uses a stack to simulate the structure of nested parentheses. Push an index or character when encountering '(' and pop when encountering ')'. The stack size represents the current nesting level. When processing characters, skip the parentheses that correspond to the outermost layer of each primitive substring. In practice, append characters only when the stack size after the operation indicates you are inside a nested level. While this approach mirrors how many stack-based parsing algorithms work, it uses additional memory proportional to the nesting depth. The runtime remains O(n) because each character is pushed and popped at most once.
Recommended for interviews: The depth counter solution is the expected answer. It shows you recognize that the stack structure is unnecessary because the nesting level alone determines whether a parenthesis is outermost. The stack approach demonstrates understanding of stack-driven parsing, but the counter approach is cleaner, uses constant space, and signals strong problem-solving instincts.
This approach uses a counter to track the depth of the current parentheses level. As you iterate through the string, increment the count whenever you see '(', and decrement it on ')'. The outermost parentheses of a primitive section occur whenever the depth transitions from 0 to 1 (for '(') or from 1 to 0 (for ')'). These should be skipped in your final result.
This C implementation iterates over the input string and uses a simple integer counter to track the depth of parenthesis nesting. When a '(' is found and the level before incrementing was greater than 0, it is part of the inner primitive string. Likewise, if before decrementing on ')' the level was greater than 1, it is part of the inner primitive. This effectively ignores the outermost parentheses.
Time Complexity: O(n), where n is the length of the string, because it processes each character exactly once.
Space Complexity: O(n), due to the storage of the output string.
This approach leverages a stack-like mechanism to mimic the actual stack process of valid parentheses. Instead of using a stack data structure, it simply uses a counter to determine valid scope levels, mimicking pushing and popping operations.
This implementation strategy using just an integer counter, simulates pushing '(' onto a 'stack' by incrementing, and popping ')' by decrementing. The openCount only allows append operations within the valid range, thus removing the outermost parentheses effectively.
Time Complexity: O(n), with n being the string length as it requires one linear pass.
Space Complexity: O(n) used for the result string.
| Approach | Complexity |
|---|---|
| Approach 1: Using a Counter to Track Depth | Time Complexity: O(n), where n is the length of the string, because it processes each character exactly once. |
| Approach 2: Stack-Based Iteration | Time Complexity: O(n), with n being the string length as it requires one linear pass. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Counter to Track Depth | O(n) | O(1) | Best choice for interviews and production code when only nesting depth matters |
| Stack-Based Iteration | O(n) | O(n) | Useful when explicitly modeling nested structure or extending to complex parsing problems |
1021. Remove Outermost Parentheses | Leetcode | Easy Problem | Strings | Stacks | Counter Approach • FastForward Coders - by Gurmeet • 55,542 views views
Watch 9 more video solutions →Practice Remove Outermost Parentheses with our built-in code editor and test cases.
Practice on FleetCode