Given a valid parentheses string s, divide the string into its primitive valid parentheses substrings. A primitive substring is a non-empty valid parentheses string that cannot be divided into smaller non-empty valid parentheses substrings.
Remove the outermost opening and closing parentheses from each primitive substring and combine the remaining parts in their original order.
Return the resulting string after removing the outermost parentheses from every primitive substring.
Example 1
Input: s = "((()))"
Output: "(())"
Explanation:
The input string is a single primitive: "((()))".
Removing the outermost layer yields: "(())".
Example 2
Input: s = "()(()())(())"
Output: "()()()"
Explanation:
Primitive decomposition: "()" + "(()())" + "(())"
After removing outermost parentheses: "" + "()()" + "()"
Final result: "()()()".
Approach
Every primitive valid parentheses string starts with an opening parenthesis and ends with its matching closing parenthesis. These two parentheses form the outermost pair and need to be removed. All parentheses between them must be kept, as they belong to the inner part of the string.
A counter variable can be used to keep track of how deeply the parentheses are nested. The counter represents the current nesting level, making it easier to identify which parentheses form the outermost pair and which belong to the inner part. By keeping track of the nesting level, the outermost parentheses can be separated from the remaining string without affecting the inner parentheses.
Algorithm
Initialize an empty string
resultand a balance counter with value0.Traverse the input string from left to right.
If the current character is
(, check the current balance. Add the character toresultonly when the balance is greater than zero. Then increase the balance by one.If the current character is
), decrease the balance by one. Add the character toresultonly when the updated balance is greater than zero.Return
resultafter processing all characters.
Dry Run
Remove Outermost Parentheses
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Function to remove outermost parentheses of every primitive substring string removeOuterParentheses(string s) { string result; int depth = 0; // Traverse the input string for (int i = 0; i < s.length(); i++) { // Handle opening parentheses if (s[i] == '(') { // Add the character only if it is not an outermost opening parenthesis if (depth > 0) { result += s[i]; } // Increase the nesting depth depth++; } // Handle closing parentheses else { // Decrease the nesting depth depth--; // Add the character only if it is not an outermost closing parenthesis if (depth > 0) { result += s[i]; } } } return result; }};// Driver code startsint main() { string s = "(()())(())"; Solution sol; // Call the function to remove outermost parentheses string result = sol.removeOuterParentheses(s); // Print the resulting string cout << result << endl; return 0;}Complexity Analysis
• Time Complexity: O(N), where N represents the length of the input string. The algorithm traverses the string exactly once, performing constant-time operations for each character.
• Space Complexity: O(N), where N represents the length of the input string. The result string can store up to N characters. The balance counter requires only O(1) auxiliary space.
Interview follow-up Questions
A primitive valid parentheses string is a non-empty valid parentheses string that cannot be split into two or more non-empty valid parentheses strings. For example, (()()) is primitive, while ()() is not.
Be the first to add a comment.