Balance a string after removing extra brackets in Java
In this tutorial, we are going to Balance a string after removing extra brackets in Java. Given a string of characters that includes both opening and closing brackets.
The task involves analyzing a string of characters with opening and closing brackets removing excess brackets to ensure balanced expression. In simple, ensuring each opening bracket is followed by a matching closing bracket in the correct order and no closing bracket appears without a matching opening bracket. The goal is to produce a modified string with all unnecessary brackets eliminated.
Example 1:
Input: Strg = “Bis)hu)m(e(ow(cat)))”
Output: Bishum(e(ow(cat)))
Explanation: In the input string, there are 2 closing brackets after the characters named Bis and hu for which there is no matching opening bracket, so we remove them. After that, we can see there are balanced matching opening and closing brackets, which means the string is balanced. Then, we print the balanced string accordingly.
Example 2:
Input: strg = “Ja(Va)t)p)oin(t)”
Output: Ja(Va)tpoin(t)
Explanation: There are two closing brackets after the characters named t and p for which there are no matching opening brackets, so we remove them. And the resultant string has appropriate opening and closing brackets, which means the string is balanced. So the output is Ja(Va)tpoin(t).
Example 3:
Input: "tu)t)o)ri(al)s"
Output: tutori(al)s
Explanation: There are 3 closing brackets after the characters named Bis and hu in the input string for which there is no matching opening bracket, so we remove them. After that, we can see that there are balanced matching opening and closing brackets, which means the string is balanced. Then, we print a balanced string in the output.
Approach: Using Brute Force
The following are the steps to solve the problem.
Step 1: Declare variables cnt for counting open brackets and nLen for storing the length of the input string.
Step 2: Now, iterate through each character of the given string using a loop.
Step 3: If an opening bracket is encountered, print it and increment the count of open brackets.
Step 4: If a closing bracket is identified and there is a matching open bracket, print it and decre
ment the count of open brackets.
Step 5: If the character is not a closing bracket, print it directly.
Step 6: If there are any open brackets left after processing the string, output the number of closing brackets required to balance the string.
FileName: BalancingAStrgByRemvExtraBrackets.java
public class BalancingAStrgByRemvExtraBrackets { // method to balance the string by removing extra brackets public static void strgBalance(String strg) { // variable to hold count of open brackets int cnt = 0, i; // variable to store input string length int nLen = strg.length(); // iterating through each character of the string for (i = 0; i < nLen; i++) { // if an opening bracket as a character if (strg.charAt(i) == '(') { // print the opening bracket System.out.print(strg.charAt(i)); cnt++; // incrementing the count of open brackets } // if the character is a closing bracket and if there exists a matching open bracket, too else if (strg.charAt(i) == ')' && cnt != 0) { System.out.print(strg.charAt(i));// printing the closing bracket cnt--; // decrement the count of opening brackets } // if the character is not a close bracket else if (strg.charAt(i) != ')') System.out.print(strg.charAt(i)); } // If still there are open brackets remaining if (cnt != 0) for (i = 0; i < cnt; i++) System.out.print(")"); } // main method public static void main(String args[]) { // provide input values String strg = "Bis)hu)m(e(ow(cat)))"; String strg1 = " Ja(Va)t)p)oin(t)"; String strg2 = "tu)t)ori(al)s"; System.out.println("The balanced Strings after removing extra brackets are:"); // method calling strgBalance(strg); System.out.println(); strgBalance(strg1); System.out.println(); strgBalance(strg2); } }
Output:
The balanced Strings after removing extra brackets are: Bishum(e(ow(cat))) Ja(Va)t(p(oin(t))) tutori(al)s
Complexity Analysis: The program iterates through each character of the input string once, takes O(n) time, and performs constant-time operations like character comparisons and printing within each iteration. Therefore, the overall time complexity of O(n) where n is the length of the input String. The space complexity is O(1) because there is no need for extra space.