Given a valid parenthesis string str consisting of lowercase alphabets, opening, and closing brackets, the task is to find the string by removing the outermost enclosing brackets such that the string remains a valid parenthesis string.
Examples:
Input: S = “(((a)(bcd)(e)))”
Output: (a)(bcd)(e)
Explanation:
The outermost enclosing brackets are: { S[0], S[1], S[13], S[14] }.
Removing the outermost enclosing brackets from str modifies str to “(a)(bcd)(e)”.
Therefore, the required output is (a)(bcd)(e).Input: str = “((ab)(bc))d”
Output: ((ab)(bc))d
Explanation:
Since no outermost enclosing brackets present in the string. Therefore, the required output is ((ab)(bc))d
Approach:The idea is to iterate over the characters of the string and count the number of consecutive opening parenthesis and closing parenthesis from both ends of the string respectively. Then, iterate over the characters present in the inner string and count the number of opening brackets needed to balance out the string. Follow the steps below to solve the problem:
Follow the below steps to solve the problem:
- Initialize a variable, say cnt = 0, to store the count of valid parenthesis such that str[cnt] == ‘(‘ and str[N – cnt – 1] == ‘)’.
- To balance the inner parenthesis of the string by the outer parenthesis, traverse the substring {str[cnt], …, str[N – cnt – 1]} and count the minimum opening or closing parenthesis required to balance the inner substring say, cntMinpar.
- Finally, update the cnt += cntMinPair and print the substring { str[cnt], …, str[N – cnt] }.
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 outermost// enclosing brackets from both endvoid removeBrakets(string str){ // Stores length of the string int n = str.length(); // Stores count of parenthesis such // that str[cnt] == cnt[N - cnt - 1] int cnt = 0; // Calculating maximum number of // bracket pair from the end side while (cnt < n && str[cnt] == '(' && str[n - cnt - 1] == ')') { // Update cnt cnt++; } // Stores minimum outer parenthesis // required to balance the substring // { str[cnt], ..., [n - cnt -1] int error = 0; // Stores count of unbalanced parenthesis // in { str[cnt], ..., [n - cnt -1] int open = 0; // Traverse the substring // { str[cnt], ..., [n - cnt -1] for(int i = cnt; i < n - cnt; i++) { // If current character is '(' if (str[i] == '(') { // Update cntUnbal open++; } // Decrease num, if the current // character is ')' else if (str[i] == ')') { // Update cntUnbal if(open>0){ open--; } else{ error++; } } } int rem=cnt-error; // Print resultant string cout << str.substr(rem, n - 2*rem) << endl; } // Driver Codeint main(){ // Input string string str = "((((a)b)(c)))"; removeBrakets(str); return 0;}// This code is contributed by susmitakundugoaldanga |
Java
// Java program to implement// the above approachimport java.util.*;import java.lang.*;class GFG { // Function to remove outermost // enclosing brackets from both end static void removeBrakets(String str) { // Stores length of the string int n = str.length(); // Stores count of parenthesis such // that str[cnt] == cnt[N - cnt - 1] int cnt = 0; // Calculating maximum number of // bracket pair from the end side while (cnt < n && str.charAt(cnt) == '(' && str.charAt(n - cnt - 1) == ')') { // Update cnt cnt++; } // Stores minimum outer parenthesis // required to balance the substring // { str[cnt], ..., [n - cnt -1] int cntMinPar = 0; // Stores count of unbalanced parenthesis // in { str[cnt], ..., [n - cnt -1] int cntUnbal = 0; // Traverse the substring // { str[cnt], ..., [n - cnt -1] for (int i = cnt; i < n - cnt; i++) { // If current character is '(' if (str.charAt(i) == '(') { // Update cntUnbal cntUnbal++; } // Decrease num, if the current // character is ')' else if (str.charAt(i) == ')') { // Update cntUnbal cntUnbal--; } // Update cntMinPar cntMinPar = Math.min( cntMinPar, cntUnbal); } // Update cnt cnt += cntMinPar; // Print resultant string System.out.println( str.substring(cnt, n - cnt)); } // Driver Code public static void main( String[] args) { // Input string String str = "((((a)b)(c)))"; removeBrakets(str); }} |
Python3
# Python3 program to implement# the above approach# Function to remove outermost# enclosing brackets from both enddef removeBrakets(str): # Stores length of the string n = len(str) # Stores count of parenthesis such # that str[cnt] == cnt[N - cnt - 1] cnt = 0 # Calculating maximum number of # bracket pair from the end side while (cnt < n and str[cnt] == '(' and str[n - cnt - 1] == ')'): # Update cnt cnt += 1 # Stores minimum outer parenthesis # required to balance the substring # { str[cnt], ..., [n - cnt -1] cntMinPar = 0 # Stores count of unbalanced parenthesis # in { str[cnt], ..., [n - cnt -1] cntUnbal = 0 # Traverse the substring # { str[cnt], ..., [n - cnt -1] for i in range(cnt, n - cnt): # If current character is '(' if (str[i] == '('): # Update cntUnbal cntUnbal += 1 # Decrease num, if the current # character is ')' elif str[i] == ')': # Update cntUnbal cntUnbal -= 1 # Update cntMinPar cntMinPar = min(cntMinPar, cntUnbal) # Update cnt cnt += cntMinPar # Print resultant string print(str[cnt: n - cnt])# Driver Codeif __name__ == '__main__': # Input string str = "((((a)b)(c)))" removeBrakets(str)# This code is contributed by mohit kumar 29 |
C#
// C# program to implement// the above approachusing System;class GFG { // Function to remove outermost // enclosing brackets from both end static void removeBrakets(String str) { // Stores length of the string int n = str.Length; // Stores count of parenthesis such // that str[cnt] == cnt[N - cnt - 1] int cnt = 0; // Calculating maximum number of // bracket pair from the end side while (cnt < n && str[cnt] == '(' && str[n - cnt - 1] == ')') { // Update cnt cnt++; } // Stores minimum outer parenthesis // required to balance the substring // { str[cnt], ..., [n - cnt -1] int cntMinPar = 0; // Stores count of unbalanced parenthesis // in { str[cnt], ..., [n - cnt -1] int cntUnbal = 0; // Traverse the substring // { str[cnt], ..., [n - cnt -1] for (int i = cnt; i < n - cnt; i++) { // If current character is '(' if (str[i] == '(') { // Update cntUnbal cntUnbal++; } // Decrease num, if the current // character is ')' else if (str[i] == ')') { // Update cntUnbal cntUnbal--; } // Update cntMinPar cntMinPar = Math.Min( cntMinPar, cntUnbal); } // Update cnt cnt += cntMinPar; // Print resultant string Console.WriteLine( str.Substring(cnt, n - cnt - 2)); } // Driver Code public static void Main(string[] args) { // Input string string str = "((((a)b)(c)))"; removeBrakets(str); }}// This code is contributed by AnkThon |
Javascript
<script>// Javascript program to implement// the above approach // Function to remove outermost// enclosing brackets from both endfunction removeBrakets(str){ // Stores length of the string var n = str.length; // Stores count of parenthesis such // that str[cnt] == cnt[N - cnt - 1] var cnt = 0; // Calculating maximum number of // bracket pair from the end side while (cnt < n && str[cnt] == '(' && str[n - cnt - 1] == ')') { // Update cnt cnt++; } // Stores minimum outer parenthesis // required to balance the substring // { str[cnt], ..., [n - cnt -1] var error = 0; // Stores count of unbalanced parenthesis // in { str[cnt], ..., [n - cnt -1] var open = 0; // Traverse the substring // { str[cnt], ..., [n - cnt -1] for(var i = cnt; i < n - cnt; i++) { // If current character is '(' if (str[i] == '(') { // Update cntUnbal open++; } // Decrease num, if the current // character is ')' else if (str[i] == ')') { // Update cntUnbal if (open > 0) { open--; } else { error++; } } } var rem = cnt - error; // Print resultant string document.write(str.substring( rem, rem + n - 2 * rem));} // Driver Code// Input stringvar str = "((((a)b)(c)))";removeBrakets(str);// This code is contributed by rutvik_56</script> |
Output:
((a)b)(c)
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
