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.The key idea in #1021 Remove Outermost Parentheses is recognizing that a valid parentheses string can be broken into smaller primitive valid groups. For each primitive group, the outermost opening ( and closing ) must be removed while keeping the inner structure intact.
A common strategy is to track the current nesting depth while scanning the string. When you encounter (, the depth increases; when you encounter ), it decreases. Characters are added to the result only when they are not the outermost boundary of a primitive group. Another intuitive method uses a stack to simulate the parentheses structure, ensuring that only inner characters are appended.
Both approaches process the string in a single pass, making them efficient for interview settings. The depth-count technique is often preferred because it avoids explicit stack storage and keeps the implementation simple.
Overall, the algorithm runs in O(n) time since each character is processed once, with minimal extra memory.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Depth Counter (Greedy String Scan) | O(n) | O(1) auxiliary |
| Stack-Based Simulation | O(n) | O(n) |
Pepcoding
Use these hints if you're stuck. Try solving on your own first.
Can you find the primitive decomposition? The number of ( and ) characters must be equal.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of parentheses processing problems frequently appear in FAANG and other top tech interviews. They test understanding of stacks, string traversal, and recognizing structural patterns in expressions.
You can solve the problem using either a stack or a simple depth counter. While a stack mirrors the natural structure of parentheses matching, a depth counter is usually preferred because it achieves the same result with less memory and simpler logic.
A primitive parentheses string is the smallest valid substring that cannot be split further into two valid parts. Identifying these groups helps isolate their outermost parentheses, making it easy to remove them while preserving the internal valid structure.
The optimal approach uses a depth counter while scanning the string. By tracking the current nesting level, you can skip the first '(' and last ')' of each primitive group while adding the remaining characters to the result. This method runs in O(n) time with constant auxiliary space.