Reduce string by removing outermost parentheses from each primitive substring
Given a string S of valid parentheses β(β and β)β, the task is to print the string obtained by removing the outermost parentheses of every primitive substring from S.
A valid parentheses substring S is primitive if it is non-empty, and cannot be split into two or more non-empty substrings which are also a valid parentheses.
Examples:
Input: S = β(()())(())()β
Output: ()()()
Explanation: The input string is β(()())(())()β can be decomposed into primitive substrings β(()())β + β(())β+β()β. After removing outermost parentheses of each primitive substrings, the string obtained is β()()β + β()β = β()()()βInput: S = β((()())(())(()(())))β
Output: (()())(())(()(()))
Approach: Follow the steps below to solve the problem:
- Initialize a variable count to store the number of opening parentheses, i.e. β(β.
- Add every β(β to the result if count is greater than 0, i.e. add all β(β after the first β(β of a primitive substring is encountered.
- Add every β)β to the result if count is greater than 1, i.e. add all β)β before the last β)β of a primitive substring is encountered.
- Finally, print the resultant string obtained.
Below is the implementation of the above approach-
C++
// C++ program to implement the // above approach #include <bits/stdc++.h> using namespace std; // Function to remove the outermost // parentheses of every primitive // substring from the given string string removeOuterParentheses(string S) { // Stores the resultant string string res; // Stores the count of // opened parentheses int count = 0; // Traverse the string for ( char c : S) { // If opening parentheses is // encountered and their // count exceeds 0 if (c == '(' && count++ > 0) // Include the character res += c; // If closing parentheses is // encountered and their // count is less than count // of opening parentheses if (c == ')' && count-- > 1) // Include the character res += c; } // Return the resultant string return res; } // Driver Code int main() { string S = "(()())(())()" ; cout << removeOuterParentheses(S); } |
Java
// Java program to implement the // above approach import java.io.*; class GFG{ // Function to remove the outermost // parentheses of every primitive // substring from the given string static String removeOuterParentheses(String S) { // Stores the resultant // string String res = "" ; // Stores the count of // opened parentheses int count = 0 ; // Traverse the string for ( int c = 0 ; c < S.length(); c++) { // If opening parentheses is // encountered and their // count exceeds 0 if (S.charAt(c) == '(' && count++ > 0 ) // Include the character res += S.charAt(c); // If closing parentheses is // encountered and their // count is less than count // of opening parentheses if (S.charAt(c) == ')' && count-- > 1 ) // Include the character res += S.charAt(c); } // Return the resultant string return res; } // Driver Code public static void main(String[] args) { String S = "(()())(())()" ; System.out.print(removeOuterParentheses(S)); } } // This code is contributed by Chitranayal |
Python3
# Python3 program to implement the # above approach # Function to remove the outermost # parentheses of every primitive # substring from the given string def removeOuterParentheses(S): # Stores the resultant string res = "" # Stores the count of # opened parentheses count = 0 # Traverse the string for c in S: # If opening parentheses is # encountered and their # count exceeds 0 if (c = = '(' and count > 0 ): # Include the character res + = c # If closing parentheses is # encountered and their # count is less than count # of opening parentheses if (c = = '(' ): count + = 1 if (c = = ')' and count > 1 ): # Include the character res + = c if (c = = ')' ): count - = 1 # Return the resultant string return res # Driver Code if __name__ = = '__main__' : S = "(()())(())()" print (removeOuterParentheses(S)) # This code is contributed by SURENDRA_GANGWAR |
C#
// C# program to implement // the above approach using System; class GFG{ // Function to remove the outermost // parentheses of every primitive // substring from the given string static string removeOuterParentheses( string S) { // Stores the resultant // string string res = "" ; // Stores the count of // opened parentheses int count = 0; // Traverse the string for ( int c = 0; c < S.Length; c++) { // If opening parentheses is // encountered and their // count exceeds 0 if (S == '(' && count++ > 0) // Include the character res += S; // If closing parentheses is // encountered and their // count is less than count // of opening parentheses if (S == ')' && count-- > 1) // Include the character res += S; } // Return the resultant string return res; } // Driver Code public static void Main() { string S = "(()())(())()" ; Console.Write(removeOuterParentheses(S)); } } // This code is contributed by sanjoy_62 |
Javascript
<script> // Javascript program to implement the // above approach // Function to remove the outermost // parentheses of every primitive // substring from the given string function removeOuterParentheses(S) { // Stores the resultant // string let res = "" ; // Stores the count of // opened parentheses let count = 0; // Traverse the string for (let c = 0; c < S.length; c++) { // If opening parentheses is // encountered and their // count exceeds 0 if (S.charAt(c) == '(' && count++ > 0) // Include the character res += S.charAt(c); // If closing parentheses is // encountered and their // count is less than count // of opening parentheses if (S.charAt(c) == ')' && count-- > 1) // Include the character res += S.charAt(c); } // Return the resultant string return res; } // Driver Code let S = "(()())(())()" ; document.write(removeOuterParentheses(S)); // This code is contributed by jana_sayantan. </script> |
()()()
Time Complexity: O(N) where n is number of elements in given string. As, we are using a loop to traverse N times so it will cost us O(N) time
Auxiliary Space: O(N), as we are using extra space for string.
The Optimal approach to remove the outermost parentheses from a string can be achieved using a simple algorithm that keeps track of the number of opening and closing parentheses encountered. Here is an optimal approach:
- Initialize two variables, open_count and close_count, to zero
- Initialize an empty string called result.
- Loop through each character c in the input string s.
- If c is an opening parenthesis, increment open_count.
- If c is a closing parenthesis, increment close_count.
- If open_count and close_count are equal and greater than zero, this means that we have encountered a complete pair of opening and closing parentheses, so we can add the substring between them to the result string.
- Reset open_count and close_count to zero.
- Return the result string.
Here is an implementation of this algorithm:
C++
// C++ Program for the above approach #include <iostream> #include <string> using namespace std; // function to remove outer parentheses string removeOuterParentheses(string s) { int openCount = 0; int closeCount = 0; string result = "" ; int start = 0; for ( int i = 0; i < s.length(); i++) { char c = s[i]; if (c == '(' ) { openCount++; } else if (c == ')' ) { closeCount++; } if (openCount == closeCount) { result += s.substr(start+1, i-start-1); start = i+1; } } // return the output string(result) return result; } // driver program to test above function int main() { // Example 1 string s1 = "(()())(())()" ; cout << removeOuterParentheses(s1) << endl; // Example 2 string s2 = "()()(()())(()())" ; cout << removeOuterParentheses(s2) << endl; // Example 3 string s3 = "((()))(())" ; cout << removeOuterParentheses(s3) << endl; return 0; } |
Java
public class Main { public static String removeOuterParentheses(String s) { int openCount = 0 ; int closeCount = 0 ; String result = "" ; int start = 0 ; for ( int i = 0 ; i < s.length(); i++) { char c = s.charAt(i); if (c == '(' ) { openCount++; } else if (c == ')' ) { closeCount++; } if (openCount == closeCount) { result += s.substring(start+ 1 , i); start = i+ 1 ; } } return result; } public static void main(String[] args) { // Example 1 String s1 = "(()())(())()" ; System.out.println(removeOuterParentheses(s1)); // Example 2 String s2 = "()()(()())(()())" ; System.out.println(removeOuterParentheses(s2)); // Example 3 String s3 = "((()))(())" ; System.out.println(removeOuterParentheses(s3)); } } // This code is contributed by Sundaram |
Python3
def remove_outer_parentheses(s): open_count = 0 close_count = 0 result = "" start = 0 for i, c in enumerate (s): if c = = "(" : open_count + = 1 elif c = = ")" : close_count + = 1 if open_count = = close_count: result + = s[start + 1 :i] start = i + 1 return result # Driver code if __name__ = = "__main__" : # Example 1 s1 = "(()())(())()" print (remove_outer_parentheses(s1)) # Example 2 s2 = "()()(()())(()())" print (remove_outer_parentheses(s2)) # Example 3 s3 = "((()))(())" print (remove_outer_parentheses(s3)) |
C#
// C# Program for the above approach using System; namespace RemoveOuterParentheses { class Program { // function to remove outer parentheses static string RemoveOuterParentheses( string s) { int openCount = 0; int closeCount = 0; string result = "" ; int start = 0; for ( int i = 0; i < s.Length; i++) { char c = s[i]; if (c == '(' ) { openCount++; } else if (c == ')' ) { closeCount++; } if (openCount == closeCount) { result += s.Substring(start + 1, i - start - 1); start = i + 1; } } // return the output string(result) return result; } // driver program to test above function static void Main( string [] args) { // Example 1 string s1 = "(()())(())()" ; Console.WriteLine(RemoveOuterParentheses(s1)); // Example 2 string s2 = "()()(()())(()())" ; Console.WriteLine(RemoveOuterParentheses(s2)); // Example 3 string s3 = "((()))(())" ; Console.WriteLine(RemoveOuterParentheses(s3)); } } } // This code is contributed by sarojmcy2w |
Javascript
function remove_outer_parentheses(s) { let open_count = 0; let close_count = 0; let result = "" ; let start = 0; for (let i = 0; i < s.length; i++) { let c = s[i]; if (c == "(" ) { open_count += 1; } else if (c == ")" ) { close_count += 1; } if (open_count == close_count) { result += s.slice(start + 1, i); start = i + 1; } } return result; } // Driver code // Example 1 let s1 = "(()())(())()" ; console.log(remove_outer_parentheses(s1)); // Example 2 let s2 = "()()(()())(()())" ; console.log(remove_outer_parentheses(s2)); // Example 3 let s3 = "((()))(())" ; console.log(remove_outer_parentheses(s3)); |
()()() ()()()() (())()
This approach has a time complexity of O(n), where n is the length of the input string s. It uses constant space, except for the output string, which is proportional to the number of valid parentheses pairs in s.
Contact Us