Problem 24: Minimum Swaps for Bracket Sequence
Problem Statement: Given a string consisting of only '[' and ']', determine the minimum number of adjacent swaps required to balance the bracket sequence. It is guaranteed that a balanced arrangement exists.
Input
A single line containing a string of '[' and ']'.
Output
Print the minimum number of swaps needed.
Examples
Input:
]][][][[
Output:
2
Solution Explanation
Method 1: Use a greedy approach by tracking the imbalance and swapping when the balance becomes negative. Method 2: Record the positions of the '[' brackets and calculate the total distance between their current positions and the positions of the balanced configuration.
Solution in C++
#include
#include
#include
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s; cin >> s;
int n = s.size();
vector pos;
for (int i = 0; i < n; i++) {
if(s[i]=='[') pos.push_back(i);
}
int count = 0, p = 0, ans = 0;
for(int i = 0; i < n; i++){
if(s[i]=='[') {
count++;
p++;
} else {
count--;
}
if(count < 0){
ans += pos[p] - i;
swap(s[i], s[pos[p]]);
p++;
count = 1;
}
}
cout << ans << "
";
return 0;
}