Minimum Swaps for Bracket Balancing
You are given a string of 2N characters consisting of N ‘[‘ brackets and N ‘]’ brackets. A string is considered balanced if it can be represented in the form S2[S1] where S1 and S2 are balanced strings. We can make an unbalanced string balanced by swapping adjacent characters. Calculate the minimum number of swaps necessary to make a string balanced.
Examples:
Input : []][][
Output : 2
First swap: Position 3 and 4
[][]][
Second swap: Position 5 and 6
[][][]
Input : [[][]]
Output : 0
The string is already balanced.
We can solve this problem by using greedy strategies. If the first X characters form a balanced string, we can neglect these characters and continue on. If we encounter a ‘]’ before the required ‘[‘, then we must start swapping elements to balance the string.
Naive Approach
Initialize sum = 0 where sum stores result. Go through the string maintaining a count of the number of ‘[‘ brackets encountered. Reduce this count when we encounter a ‘]’ character. If the count hits negative, then we must start balancing the string.
Let index ‘i’ represent the position we are at. We now move forward to the next ‘[‘ at index j. Increase sum by j – i. Move the ‘[‘ at position j, to position i, and shift all other characters to the right. Set the count back to 1 and continue traversing the string. In the end, ‘sum’ will have the required value.
Code-
// C++ program to count swaps required to balance string
#include<bits/stdc++.h>
using namespace std;
// Function to calculate swaps required
int swapCount(string s)
{
//To store answer
int ans=0;
//To store count of '['
int count=0;
//Size of string
int n=s.size();
//Traverse over the string
for(int i=0;i<n;i++){
//When '[' encounters
if(s[i]=='['){count++;}
//when ']' encounters
else{count--;}
//When count becomes less than 0
if(count<0){
//Start searching for '[' from (i+1)th index
int j=i+1;
while(j<n){
//When jth index contains '['
if(s[j]=='['){break;}
j++;
}
//Increment answer
ans+=j-i;
//Set Count to 1 again
count=1;
//Bring character at jth position to ith position
//and shift all character from i to j-1
//towards right
char ch=s[j];
for(int k=j;k>i;k--){
s[k]=s[k-1];
}
s[i]=ch;
}
}
return ans;
}
// Driver code
int main()
{
string s = "[]][][";
cout << swapCount(s) << "\n";
s = "[[][]]";
cout << swapCount(s) << "\n";
return 0;
}
// Java program to count swaps required to balance string
public class GFG {
// Function to calculate swaps required
static int swapCount(String s) {
//To store answer
int ans = 0;
//To store count of '['
int count = 0;
//Size of string
int n = s.length();
//Traverse over the string
for (int i = 0; i < n; i++) {
//When '[' encounters
if (s.charAt(i) == '[')
count++;
//when ']' encounters
else
count--;
//When count becomes less than 0
if (count < 0) {
//Start searching for '[' from (i+1)th index
int j = i + 1;
while (j < n) {
//When jth index contains '['
if (s.charAt(j) == '[')
break;
j++;
}
//Increment answer
ans += j - i;
//Set Count to 1 again
count = 1;
//Bring character at jth position to ith position
//and shift all character from i to j-1
//towards right
char ch = s.charAt(j);
StringBuilder newString = new StringBuilder(s);
for (int k = j; k > i; k--) {
newString.setCharAt(k, s.charAt(k - 1));
}
newString.setCharAt(i, ch);
s = newString.toString();
}
}
return ans;
}
// Driver code
public static void main(String[] args) {
String s = "[]][][";
System.out.println(swapCount(s));
s = "[[][]]";
System.out.println(swapCount(s));
}
}
def swap_count(s):
# To store the answer
ans = 0
# To store the count of '['
count = 0
# Size of the string
n = len(s)
# Traverse over the string
for i in range(n):
# When '[' encounters
if s[i] == '[':
count += 1
# When ']' encounters
else:
count -= 1
# When count becomes less than 0
if count < 0:
# Start searching for '[' from (i+1)th index
j = i + 1
while j < n:
# When jth index contains '['
if s[j] == '[':
break
j += 1
# Increment the answer
ans += j - i
# Set count to 1 again
count = 1
# Bring the character at jth position to ith position
# and shift all characters from i to j-1
# towards the right
ch = s[j]
for k in range(j, i, -1):
s[k] = s[k - 1]
s[i] = ch
return ans
# Driver code
if __name__ == "__main__":
s = "[]][]["
print(swap_count(list(s)))
s = "[[][]]"
print(swap_count(list(s)))
using System;
class Program
{
// Function to calculate swaps required
static int SwapCount(string s)
{
// To store answer
int ans = 0;
// To store count of '['
int count = 0;
// Size of string
int n = s.Length;
// Traverse over the string
for (int i = 0; i < n; i++)
{
// When '[' encounters
if (s[i] == '[')
{
count++;
}
// When ']' encounters
else
{
count--;
}
// When count becomes less than 0
if (count < 0)
{
// Start searching for '[' from (i+1)th index
int j = i + 1;
while (j < n)
{
// When jth index contains '['
if (s[j] == '[')
{
break;
}
j++;
}
// Increment answer
ans += j - i;
// Set Count to 1 again
count = 1;
// Bring character at jth position to ith position
// and shift all characters from i to j-1
// towards right
char ch = s[j];
for (int k = j; k > i; k--)
{
s = s.Remove(k, 1);
s = s.Insert(k, s[k - 1].ToString());
}
s = s.Remove(i, 1);
s = s.Insert(i, ch.ToString());
}
}
return ans;
}
// Driver code
static void Main(string[] args)
{
string s = "[]][][";
Console.WriteLine(SwapCount(s));
s = "[[][]]";
Console.WriteLine(SwapCount(s));
}
}
function GFG(s) {
// To store answer
let ans = 0;
// To store count of '['
let count = 0;
// Traverse over the string
for (let i = 0; i < s.length; i++) {
// When '[' encounters
if (s[i] === '[') {
count++;
}
// When ']' encounters
else {
count--;
}
// When count becomes less than 0
if (count < 0) {
// Start searching for
// '[' from the beginning
for (let j = 0; j < i; j++) {
// When jth index contains '['
if (s[j] === '[') {
ans += i - j;
// Swap characters to balance the string
let temp = s.substring(0, j) + s[i] + s.substring(j + 1, i) + s[j] + s.substring(i + 1);
s = temp;
break;
}
}
// Reset the count
count = 1;
}
}
return ans;
}
// Driver code
let s1 = "[]][][";
console.log(GFG(s1)); // Output: 2
let s2 = "[[][]]";
console.log(GFG(s2)); // Output: 0
Output
2 0
Time Complexity = O(N^2), one loop is for traversing the string and another loop in finding the next ‘[‘ when the count becomes less than 0 and making the string ready for the next step
Extra Space = O(1), because no extra space has been used
Optimized approach
We can initially go through the string and store the positions of ‘[‘ in a vector say ‘pos‘. Initialize ‘p’ to 0. We shall use p to traverse the vector ‘pos’. Similar to the naive approach, we maintain a count of encountered ‘[‘ brackets. When we encounter a ‘[‘ we increase the count and increase ‘p’ by 1. When we encounter a ‘]’ we decrease the count. If the count ever goes negative, this means we must start swapping. The element pos[p] tells us the index of the next ‘[‘. We increase the sum by pos[p] – i, where i is the current index. We can swap the elements in the current index and pos[p] and reset the count to 1 and increment p so that it pos[p] indicates to the next ‘[‘.
Since we have converted a step that was O(N) in the naive approach, to an O(1) step, our new time complexity reduces.
Time Complexity = O(N)
Extra Space = O(N)
// C++ program to count swaps required to balance string
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Function to calculate swaps required
long swapCount(string s)
{
// Keep track of '['
vector<int> pos;
for (int i = 0; i < s.length(); ++i)
if (s[i] == '[')
pos.push_back(i);
int count = 0; // To count number of encountered '['
int p = 0; // To track position of next '[' in pos
long sum = 0; // To store result
for (int i = 0; i < s.length(); ++i)
{
// Increment count and move p to next position
if (s[i] == '[')
{
++count;
++p;
}
else if (s[i] == ']')
--count;
// We have encountered an unbalanced part of string
if (count < 0)
{
// Increment sum by number of swaps required
// i.e. position of next '[' - current position
sum += pos[p] - i;
swap(s[i], s[pos[p]]);
++p;
// Reset count to 1
count = 1;
}
}
return sum;
}
// Driver code
int main()
{
string s = "[]][][";
cout << swapCount(s) << "\n";
s = "[[][]]";
cout << swapCount(s) << "\n";
return 0;
}
// Java program to count swaps
// required to balance string
import java.util.*;
class GFG{
// Function to calculate swaps required
public static long swapCount(String s)
{
// Keep track of '['
Vector<Integer> pos = new Vector<Integer>();
for(int i = 0; i < s.length(); ++i)
if (s.charAt(i) == '[')
pos.add(i);
// To count number of encountered '['
int count = 0;
// To track position of next '[' in pos
int p = 0;
// To store result
long sum = 0;
char[] S = s.toCharArray();
for(int i = 0; i < s.length(); ++i)
{
// Increment count and move p
// to next position
if (S[i] == '[')
{
++count;
++p;
}
else if (S[i] == ']')
--count;
// We have encountered an
// unbalanced part of string
if (count < 0)
{
// Increment sum by number of
// swaps required i.e. position
// of next '[' - current position
sum += pos.get(p) - i;
char temp = S[i];
S[i] = S[pos.get(p)];
S[pos.get(p)] = temp;
++p;
// Reset count to 1
count = 1;
}
}
return sum;
}
// Driver code
public static void main(String[] args)
{
String s = "[]][][";
System.out.println(swapCount(s));
s = "[[][]]";
System.out.println(swapCount(s));
}
}
// This code is contributed by divyesh072019
# Python3 Program to count
# swaps required to balance
# string
# Function to calculate
# swaps required
def swapCount(s):
# Keep track of '['
pos = []
for i in range(len(s)):
if(s[i] == '['):
pos.append(i)
# To count number
# of encountered '['
count = 0
# To track position
# of next '[' in pos
p = 0
# To store result
sum = 0
s = list(s)
for i in range(len(s)):
# Increment count and
# move p to next position
if(s[i] == '['):
count += 1
p += 1
elif(s[i] == ']'):
count -= 1
# We have encountered an
# unbalanced part of string
if(count < 0):
# Increment sum by number
# of swaps required
# i.e. position of next
# '[' - current position
sum += pos[p] - i
s[i], s[pos[p]] = (s[pos[p]],
s[i])
p += 1
# Reset count to 1
count = 1
return sum
# Driver code
s = "[]][]["
print(swapCount(s))
s = "[[][]]"
print(swapCount(s))
# This code is contributed by avanitrachhadiya2155
// C# program to count swaps
// required to balance string
using System.IO;
using System;
using System.Collections;
using System.Collections.Generic;
class GFG{
// Function to calculate swaps required
static long swapCount(string s)
{
// Keep track of '['
List<int> pos = new List<int>();
for(int i = 0; i < s.Length; i++)
{
if (s[i] == '[')
{
pos.Add(i);
}
}
// To count number of encountered '['
int count = 0;
// To track position of next '[' in pos
int p = 0;
// To store result
long sum = 0;
char[] S = s.ToCharArray();
for(int i = 0; i < S.Length; i++)
{
// Increment count and move p
// to next position
if (S[i] == '[')
{
++count;
++p;
}
else if (S[i] == ']')
{
--count;
}
// We have encountered an
// unbalanced part of string
if (count < 0)
{
// Increment sum by number of
// swaps required i.e. position
// of next '[' - current position
sum += pos[p]-i;
char temp = S[i];
S[i] = S[pos[p]];
S[pos[p]] = temp;
++p;
// Reset count to 1
count = 1;
}
}
return sum;
}
// Driver code
static void Main()
{
string s = "[]][][";
Console.WriteLine(swapCount(s));
s = "[[][]]";
Console.WriteLine(swapCount(s));
}
}
// This code is contributed by rag2127
// JavaScript program to count swaps
// required to balance string
// Function to calculate swaps required
function swapCount(s)
{
// Keep track of '['
let pos = [];
for(let i = 0; i < s.length; ++i)
if (s[i] == '[')
pos.push(i);
// To count number of encountered '['
let count = 0;
// To track position of next '[' in pos
let p = 0;
// To store result
let sum = 0;
let S = s.split('');
for(let i = 0; i < s.length; ++i)
{
// Increment count and move p
// to next position
if (S[i] == '[')
{
++count;
++p;
}
else if (S[i] == ']')
--count;
// We have encountered an
// unbalanced part of string
if (count < 0)
{
// Increment sum by number of
// swaps required i.e. position
// of next '[' - current position
sum += pos[p] - i;
let temp = S[i];
S[i] = S[pos[p]];
S[pos[p]] = temp;
++p;
// Reset count to 1
count = 1;
}
}
return sum;
}
// Driver Code
let s = "[]][][";
console.log(swapCount(s) + "<br/>");
s = "[[][]]";
console.log(swapCount(s));
Output
2 0
Time Complexity: O(N)
Auxiliary Space: O(N)
Another Method:
We can do without having to store the positions of ‘[‘.
Below is the implementation :
// C++ program to count swaps required
// to balance string
#include <bits/stdc++.h>
using namespace std;
long swapCount(string chars)
{
// Stores total number of Left and
// Right brackets encountered
int countLeft = 0, countRight = 0;
// swap stores the number of swaps
// required imbalance maintains
// the number of imbalance pair
int swap = 0 , imbalance = 0;
for(int i = 0; i < chars.length(); i++)
{
if (chars[i] == '[')
{
// Increment count of Left bracket
countLeft++;
if (imbalance > 0)
{
// swaps count is last swap count + total
// number imbalanced brackets
swap += imbalance;
// imbalance decremented by 1 as it solved
// only one imbalance of Left and Right
imbalance--;
}
}
else if(chars[i] == ']' )
{
// Increment count of Right bracket
countRight++;
// imbalance is reset to current difference
// between Left and Right brackets
imbalance = (countRight - countLeft);
}
}
return swap;
}
// Driver code
int main()
{
string s = "[]][][";
cout << swapCount(s) << endl;
s = "[[][]]";
cout << swapCount(s) << endl;
return 0;
}
// This code is contributed by divyeshrabadiya07
// Java Program to count swaps required to balance string
public class BalanceParan
{
static long swapCount(String s)
{
char[] chars = s.toCharArray();
// stores total number of Left and Right
// brackets encountered
int countLeft = 0, countRight = 0;
// swap stores the number of swaps required
//imbalance maintains the number of imbalance pair
int swap = 0 , imbalance = 0;
for(int i =0; i< chars.length; i++)
{
if(chars[i] == '[')
{
// increment count of Left bracket
countLeft++;
if(imbalance > 0)
{
// swaps count is last swap count + total
// number imbalanced brackets
swap += imbalance;
// imbalance decremented by 1 as it solved
// only one imbalance of Left and Right
imbalance--;
}
} else if(chars[i] == ']' )
{
// increment count of Right bracket
countRight++;
// imbalance is reset to current difference
// between Left and Right brackets
imbalance = (countRight-countLeft);
}
}
return swap;
}
// Driver code
public static void main(String args[])
{
String s = "[]][][";
System.out.println(swapCount(s) );
s = "[[][]]";
System.out.println(swapCount(s) );
}
}
// This code is contributed by Janmejaya Das.
# Python3 program to count swaps required to
# balance string
def swapCount(s):
# Swap stores the number of swaps
# required imbalance maintains the
# number of imbalance pair
swap = 0
imbalance = 0;
for i in s:
if i == '[':
# Decrement the imbalance
imbalance -= 1
else:
# Increment imbalance
imbalance += 1
if imbalance > 0:
swap += imbalance
return swap
# Driver code
s = "[]][][";
print(swapCount(s))
s = "[[][]]";
print(swapCount(s))
# This code is contributed by Prateek Gupta and improved by Anvesh Govind Saxena
// C# Program to count swaps required
// to balance string
using System;
class GFG
{
public static long swapCount(string s)
{
char[] chars = s.ToCharArray();
// stores the total number of Left and
// Right brackets encountered
int countLeft = 0, countRight = 0;
// swap stores the number of swaps
// required imbalance maintains the
// number of imbalance pair
int swap = 0, imbalance = 0;
for (int i = 0; i < chars.Length; i++)
{
if (chars[i] == '[')
{
// increment count of Left bracket
countLeft++;
if (imbalance > 0)
{
// swaps count is last swap count + total
// number imbalanced brackets
swap += imbalance;
// imbalance decremented by 1 as it solved
// only one imbalance of Left and Right
imbalance--;
}
}
else if (chars[i] == ']')
{
// increment count of Right bracket
countRight++;
// imbalance is reset to current difference
// between Left and Right brackets
imbalance = (countRight - countLeft);
}
}
return swap;
}
// Driver code
public static void Main(string[] args)
{
string s = "[]][][";
Console.WriteLine(swapCount(s));
s = "[[][]]";
Console.WriteLine(swapCount(s));
}
}
// This code is contributed by Shrikant13
// Javascript Program to count swaps required
// to balance string
function swapCount(s)
{
let chars = s.split('');
// stores the total number of Left and
// Right brackets encountered
let countLeft = 0, countRight = 0;
// swap stores the number of swaps
// required imbalance maintains the
// number of imbalance pair
let swap = 0, imbalance = 0;
for (let i = 0; i < chars.length; i++)
{
if (chars[i] == '[')
{
// increment count of Left bracket
countLeft++;
if (imbalance > 0)
{
// swaps count is last swap count + total
// number imbalanced brackets
swap += imbalance;
// imbalance decremented by 1 as it solved
// only one imbalance of Left and Right
imbalance--;
}
}
else if (chars[i] == ']')
{
// increment count of Right bracket
countRight++;
// imbalance is reset to current difference
// between Left and Right brackets
imbalance = (countRight - countLeft);
}
}
return swap;
}
let s = "[]][][";
console.log(swapCount(s) + "</br>");
s = "[[][]]";
console.log(swapCount(s));
// This code is contributed by suresh07.
Output
2 0
Time Complexity :O(N)
Auxiliary Space : O(1)
Contact Us