A balanced sequence is defined as a string in which for every opening bracket there are 2 continuous closing brackets. Thus, {}}, {{}}}}, {{}}{}}}} are balanced, whereas }}{, {} are not balanced.
Now given a sequence of brackets (‘{‘ and ‘}’), and you can perform only one operation on that sequence, i.e., either insert an opening or closing bracket at any position. You have to tell the minimum number of operations required to make the given sequence balanced.
Input: str = “{}}”
Output: 0
The sequence is already balanced.
Input: str = “{}{}}}”
Output: 3
The updated sequence will be “{}}{}}{}}”.
Approach: For making a balanced sequence, two continuous closing brackets are required for every opening bracket. There can be 3 cases:
- When the current character is an opening bracket: If the previous character is not a closing bracket, then simply insert the opening bracket to stack, else there is a need for a closing bracket that will cost one operation.
- If the stack is empty and the current character is a closing bracket: In this case, one opening bracket is required that will cost one operation and insert that opening bracket to the stack.
- If the stack is not empty but the current character is a closing bracket: Here, only the count of closing brackets is required. If it is 2, then remove one opening bracket from the stack, else increment the count of the closing bracket.
At the end of the string, if the stack is not empty, then the required count of closing brackets will be ((2 * size of the stack) – current count of closing brackets).
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the minimum operations requiredint minOperations(string s, int len){ int operationCnt = 0; stack<char> st; int cntClosing = 0; for (int i = 0; i < len; i++) { // Condition where we got only one closing // bracket instead of 2, here we have to // add one more closing bracket to // make the sequence balanced if (s[i] == '{') { if (cntClosing > 0) { // Add closing bracket that // costs us one operation operationCnt++; // Remove the top opening bracket because // we got the 1 opening and 2 // continuous closing brackets st.pop(); } // Inserting the opening bracket to stack st.push(s[i]); // After making the sequence balanced // closing is now set to 0 cntClosing = 0; } else if (st.empty()) { // Case when there is no opening bracket // the sequence starts with a closing bracket // and one opening bracket is required // Now we have one opening and one closing bracket st.push('{'); // Add opening bracket that // costs us one operation operationCnt++; // Assigning 1 to cntClosing because // we have one closing bracket cntClosing = 1; } else { cntClosing = (cntClosing + 1) % 2; // Case where we got two continuous closing brackets // Need to pop one opening bracket from stack top if (cntClosing == 0) { st.pop(); } } } // Condition where stack is not empty // This is the case where we have // only opening brackets // (st.size() * 2) will give us the total // closing bracket needed // cntClosing is the count of closing // bracket that we already have operationCnt += st.size() * 2 - cntClosing; return operationCnt;}// Driver codeint main(){ string str = "}}{"; int len = str.length(); cout << minOperations(str, len); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG{// Function to return the// minimum operations requiredstatic int minOperations(String s, int len){ int operationCnt = 0; Stack<Character> st = new Stack<Character>(); int cntClosing = 0; for(int i = 0; i < len; i++) { // Condition where we got only one // closing bracket instead of 2, // here we have to add one more // closing bracket to make the // sequence balanced if (s.charAt(i) == '{') { if (cntClosing > 0) { // Add closing bracket that // costs us one operation operationCnt++; // Remove the top opening bracket // because we got the 1 opening // and 2 continuous closing brackets st.pop(); } // Inserting the opening bracket to stack st.add(s.charAt(i)); // After making the sequence balanced // closing is now set to 0 cntClosing = 0; } else if (st.isEmpty()) { // Case when there is no opening // bracket the sequence starts // with a closing bracket and // one opening bracket is required // Now we have one opening and one // closing bracket st.add('{'); // Add opening bracket that // costs us one operation operationCnt++; // Assigning 1 to cntClosing because // we have one closing bracket cntClosing = 1; } else { cntClosing = (cntClosing + 1) % 2; // Case where we got two continuous // closing brackets need to pop one // opening bracket from stack top if (cntClosing == 0) { st.pop(); } } } // Condition where stack is not empty // This is the case where we have only // opening brackets (st.size() * 2) // will give us the total closing // bracket needed cntClosing is the // count of closing bracket that // we already have operationCnt += st.size() * 2 - cntClosing; return operationCnt;}// Driver codepublic static void main(String[] args){ String str = "}}{"; int len = str.length(); System.out.print(minOperations(str, len));}}// This code is contributed by amal kumar choubey |
Python3
# Python3 implementation # of the approach# Function to return the# minimum operations requireddef minOperations(s, length): operationCnt = 0 stack = [] # Built-in Python3 list to implement stack cntClosing = 0 for i in range(0, length): # Condition where we got only one # closing bracket instead of 2, # here we have to add one more # closing bracket to make the # sequence balanced if (s[i] == '{'): if (cntClosing > 0): # Add closing bracket that # costs us one operation operationCnt += 1 # Remove the top opening bracket # because we got the 1 opening # and 2 continuous closing brackets stack.pop() # Inserting the opening bracket to stack stack.append(s[i]) # After making the sequence balanced # closing is now set to 0 cntClosing = 0 elif not stack: # Case when there is no opening # bracket the sequence starts # with a closing bracket and # one opening bracket is required # Now we have one opening and one # closing bracket stack.append('{') # Add opening bracket that # costs us one operation operationCnt += 1 # Assigning 1 to cntClosing because # we have one closing bracket cntClosing = 1 else: cntClosing = (cntClosing + 1) % 2 # Case where we got two continuous # closing brackets need to pop one # opening bracket from stack top if (cntClosing == 0): stack.pop() # Condition where stack is not empty # This is the case where we have only # opening brackets (st.size() * 2) # will give us the total closing # bracket needed cntClosing is the # count of closing bracket that # we already have operationCnt += len(stack) * 2 - cntClosing return operationCnt# Driver codeif __name__ == '__main__': string = "}}{" print(minOperations(string, len(string)))# This code is contributed by gauravrajput1 |
C#
// C# implementation of // the above approachusing System;using System.Collections.Generic;class GFG{// Function to return the// minimum operations requiredstatic int minOperations(String s, int len){ int operationCnt = 0; Stack<char> st = new Stack<char>(); int cntClosing = 0; for(int i = 0; i < len; i++) { // Condition where we got only one // closing bracket instead of 2, // here we have to add one more // closing bracket to make the // sequence balanced if (s[i] == '{') { if (cntClosing > 0) { // Add closing bracket that // costs us one operation operationCnt++; // Remove the top opening bracket // because we got the 1 opening // and 2 continuous closing brackets st.Pop(); } // Inserting the opening bracket to stack st.Push(s[i]); // After making the sequence balanced // closing is now set to 0 cntClosing = 0; } else if (st.Count != 0) { // Case when there is no opening // bracket the sequence starts // with a closing bracket and // one opening bracket is required // Now we have one opening and one // closing bracket st.Push('{'); // Add opening bracket that // costs us one operation operationCnt++; // Assigning 1 to cntClosing because // we have one closing bracket cntClosing = 1; } else { cntClosing = (cntClosing + 1) % 2; // Case where we got two continuous // closing brackets need to pop one // opening bracket from stack top if (cntClosing == 0 && st.Count != 0) { st.Pop(); } } } // Condition where stack is not empty // This is the case where we have only // opening brackets (st.Count * 2) // will give us the total closing // bracket needed cntClosing is the // count of closing bracket that // we already have operationCnt += st.Count * 2 - cntClosing + 1; return operationCnt;}// Driver codepublic static void Main(String[] args){ String str = "}}{"; int len = str.Length; Console.Write(minOperations(str, len));}}// This code is contributed by gauravrajput1 |
Javascript
<script>// Javascript implementation of the approach// Function to return the minimum operations requiredfunction minOperations(s, len){ var operationCnt = 0; var st = []; var cntClosing = 0; for (var i = 0; i < len; i++) { // Condition where we got only one closing // bracket instead of 2, here we have to // add one more closing bracket to // make the sequence balanced if (s[i] == '{') { if (cntClosing > 0) { // Add closing bracket that // costs us one operation operationCnt++; // Remove the top opening bracket because // we got the 1 opening and 2 // continuous closing brackets st.pop(); } // Inserting the opening bracket to stack st.push(s[i]); // After making the sequence balanced // closing is now set to 0 cntClosing = 0; } else if (st.length==0) { // Case when there is no opening bracket // the sequence starts with a closing bracket // and one opening bracket is required // Now we have one opening and one closing bracket st.push('{'); // Add opening bracket that // costs us one operation operationCnt++; // Assigning 1 to cntClosing because // we have one closing bracket cntClosing = 1; } else { cntClosing = (cntClosing + 1) % 2; // Case where we got two continuous closing brackets // Need to pop one opening bracket from stack top if (cntClosing == 0) { st.pop(); } } } // Condition where stack is not empty // This is the case where we have // only opening brackets // (st.size() * 2) will give us the total // closing bracket needed // cntClosing is the count of closing // bracket that we already have operationCnt += st.length * 2 - cntClosing; return operationCnt;}// Driver codevar str = "}}{";var len = str.length;document.write( minOperations(str, len));</script> |
Output:
3
Time Complexity: O(n)
Auxiliary Space: O(n)
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!
