Remove Outermost Parentheses
Problem Description
A valid parentheses string is either empty "", "(" + A + ")", or A + B, where A and B are valid parentheses strings, and + represents string concatenation.
For example, "", "()", "(())()", 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.
Explanation
The question is about processing a string of parentheses '(' and ')', where the input string is guaranteed to be valid. A valid string of parentheses means that:
- Every opening parenthesis '(' has a matching closing parenthesis ')'.
- The order of parentheses is correct.
The task is to remove the outermost pair of parentheses from every "primitive" valid substring of the input string.
Primitive valid parentheses string:
- A substring that is valid and cannot be split into two smaller valid parts.
- Example: "()" and "(())" are primitive, but "(()())" is not primitive.
We have to break the input string into its primitive parts. Then, remove the outermost parentheses (first '(' and last ')') from each primitive part. Next, Combine the results to form the final string.
Examples
Input: s = "(()())(())"
Output: "()()()"
Explanation:
The input string is "(()())(())", with primitive decomposition "(()())" + "(())".
After removing outer parentheses of each part, this is "()()" + "()" = "()()()".
Input: s = "(()())(())(()(()))"
Output: "()()()()(())"
Explanation:
The input string is "(()())(())(()(()))", with primitive decomposition "(()())" + "(())" + "(()(()))".
After removing outer parentheses of each part, this is "()()" + "()" + "()(())" = "()()()()(())".
Input: s = "()()"
Output: ""
Explanation:
The input string is "()()", with primitive decomposition "()" + "()".
After removing outer parentheses of each part, this is "" + "" = "".
The solution for the Brute Force Approach involves logical thinking rather than applying the Brute Force Approach. Let's build our intuition step by step and finalise the approach!
Optimal Approach
Intuition
Let's take an example that observe ehat did we notice,
If the input is "(()())(())", the primitive parts are:
- "(()())" → remove outer parentheses → "()()".
- "(())" → remove outer parentheses → "()".
Final output: "()()()".
The first primitive part is (()()). We removed the outer parentheses to get "()()".
Similarly, removing the outer parentheses for "(())", we get "()".
But, how can we know that a parentheses is outer or not??
Is it possible by knowing it's depth ? Depth means the number of nested parentheses.
Now, let's figure out one more thing.
If the string s= "(())".
The answer is = "()".
How we got this.
At 0th character i.e '(', the depth becomes 1 i.e. depth=1.
At 1st character i.e '(', depth=1+1=2,
At 2nd character i.e. ')' depth= 2-1=1. (Please refer to the mentioned article in the callout)
At 3rd character i.e. ')' depth=1-1=0.
Did we observe, that the outermost pair of parentheses were lying at
depth =1 and depth =0?
Yes, it's an important observation. This means whenever, our depth becomes 0 or 1, we mustn't include those. All other parentheses are part of inner levels and should be kept.
So, our logic is clear, we will iterate over the string , we will maintain a counter to know the depth. Whenever we encounter a '(' we will increase the counter and check if the counter value is greater than 0 or not. If it is, we will add the character into the string.
Similarly, when we encounter ')' , we will decrement the counter and if the counter values is greater than 1, we will add the character to the answer string or else exclude it.
Let's see how we can code it up !!
Approach
Initialize: ans as an empty string (to store the result). depth as 0 (to track the depth of parentheses nesting).
Iterate through each character in the string s:
If the current character curr is '(':
- Increment depth (go deeper into the nesting).
- If depth > 1, add '(' to ans (because it’s not the outermost parenthesis).
If the current character curr is ')':
- If depth > 1, add ')' to ans (because it’s not the outermost parenthesis).
- Decrement depth (move back up the nesting).
Return ans as the final result.
Dry-Run
Input: "(()())"
Output: "()()"
Step 1: ans = "", depth = 0.
Step 2: Iterate through "(()())":
- curr = '(', depth++ → depth = 1 → Outer parenthesis, skip.
- curr = '(', depth++ → depth = 2 → Add '(' to ans: ans = "(".
- curr = ')', depth-- → Add ')' to ans: ans = "()", depth = 1.
- curr = '(', depth++ → depth = 2 → Add '(' to ans: ans = "()(".
- curr = ')', depth-- → Add ')' to ans: ans = "()()", depth = 1.
- curr = ')', depth-- → Outer parenthesis, skip.
Step 3: Return "()()".
Optimal Code in all Languages.
1. C++ Try on Compiler
class Solution {
public:
string removeOuterParentheses(string s) {
// Initialize result string
string ans = "";
// Initialize depth counter
int depth = 0;
// Iterate through the string characters
for (char curr : s) {
// Append '(' if the depth before incrementing is greater than 0
if (curr == '(' && depth++ > 0) {
ans += curr;
}
// Append ')' if the depth before decrementing is greater than 1
if (curr == ')' && depth-- > 1) {
ans += curr;
}
}
// Return the final result
return ans;
}
};
2. Java Try on Compiler
class Solution {
public String removeOuterParentheses(String s) {
// Initialize a StringBuilder to store the result
StringBuilder ans = new StringBuilder("");
// Initialize depth counter
int depth = 0;
// Iterate through the string characters
for (int i = 0; i < s.length(); i++) {
// Get the current character
char curr = s.charAt(i);
// Append '(' if the depth before incrementing is greater than 0
if (curr == '(' && depth++ > 0) {
ans.append(curr);
}
// Append ')' if the depth before decrementing is greater than 1
if (curr == ')' && depth-- > 1) {
ans.append(curr);
}
}
// Return the final result as a string
return ans.toString();
}
}
3. Python Try on Compiler
class Solution:
def removeOuterParentheses(self, s: str) -> str:
# Initialize result string
ans = []
# Initialize depth counter
depth = 0
# Iterate through the string characters
for curr in s:
# Append '(' if the depth before incrementing is greater than 0
if curr == '(' and depth > 0:
ans.append(curr)
# Adjust depth
depth += 1 if curr == '(' else -1
# Append ')' if the depth before decrementing is greater than 1
if curr == ')' and depth > 0:
ans.append(curr)
# Return the final result
return ''.join(ans)4. JavaScript Try on Compiler
class Solution {
removeOuterParentheses(s) {
// Initialize result string
let ans = "";
// Initialize depth counter
let depth = 0;
// Iterate through the string characters
for (let i = 0; i < s.length; i++) {
// Get the current character
let curr = s[i];
// Append '(' if the depth before incrementing is greater than 0
if (curr === '(' && depth++ > 0) {
ans += curr;
}
// Append ')' if the depth before decrementing is greater than 1
if (curr === ')' && depth-- > 1) {
ans += curr;
}
}
// Return the final result
return ans;
}
}
Time Complexity: O(n)
Iteration Over the String:
The function iterates over the string s once in a single loop. This takes O(n), where n is the length of the string s.
Inserting character to the final string takes O(1) runtime.
So, the overall time complexity is O(n) + O(1) = O(n)
Space Complexity: O(1)
Auxiliary Space Complexity refers to the extra space required by an algorithm other than the input space.
Depth Counter (depth): A single integer variable to track the current depth of parentheses. This takes O(1) space.
Intermediate Variables: Only a constant number of intermediate variables are used (e.g., curr, i).
Overall Auxiliary Space is O(1) for all languages.
Total Space Complexity
Input String (s): The input string occupies O(n) space, but this is already provided and not counted as additional space.
Result Storage (ans): In the worst case, the output is a string containing all characters except the outer parentheses. This can take O(n) additional space if all parentheses are valid and nested.
Auxiliary space complexity: O(1)
Overall Total space complexity is: O(n) + O(1) = O(n)
Learning Tip
For learning purpose, did you imagine how can we build the logic using a Stack.
A string is a valid parentheses string (denoted VPS) if and only if it consists of "(" and ")" characters only, and:
- It is the empty string, or
- It can be written as AB (A concatenated with B), where A and B are VPS's, or
- It can be written as (A), where A is a VPS.
We can similarly define the nesting depth depth(S) of any VPS S as follows:
- depth("") = 0
- depth(A + B) = max(depth(A), depth(B)), where A and B are VPS's
- depth("(" + A + ")") = 1 + depth(A), where A is a VPS.
For example, "", "()()", and "()(()())" are VPS's (with nesting depths 0, 1, and 2), and ")(" and "(()" are not VPS's.
Given a VPS seq, split it into two disjoint subsequences A and B, such that A and B are VPS's (and A.length + B.length = seq.length).
Now choose any such A and B such that max(depth(A), depth(B)) is the minimum possible value.
Return an answer array (of length seq.length) that encodes such a choice of A and B: answer[i] = 0 if seq[i] is part of A, else answer[i] = 1. Note that even though multiple answers may exist, you may return any of them.
A parentheses string is a non-empty string consisting only of '(' and ')'. It is valid if any of the following conditions is true:
- It is ().
- It can be written as AB (A concatenated with B), where A and B are valid parentheses strings.
- It can be written as (A), where A is a valid parentheses string.
You are given a parentheses string s and a string locked, both of length n. locked is a binary string consisting only of '0's and '1's. For each index i of locked,
- If locked[i] is '1', you cannot change s[i].
- But if locked[i] is '0', you can change s[i] to either '(' or ')'.
Return true if you can make s a valid parentheses string. Otherwise, return false.