Remove Outermost Parentheses

14
0

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 result and a balance counter with value 0.

  • Traverse the input string from left to right.

  • If the current character is (, check the current balance. Add the character to result only 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 to result only when the updated balance is greater than zero.

  • Return result after processing all characters.

Dry Run

Remove Outermost Parentheses

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 starts
int 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.

StringTCS NQT

Read Similar Blogs

Comments0