Problem Statement:
You are given a string with 2N characters consisting of equally “[” and “]” brackets.
They are unbalanced, you need to find the minimum swaps required for them to make balanced.
Example
Input : []][][ Output : 2 Swap position 3 and 4 [][]][ Then swap position 5 and 6 [][][]
Solution
The solution is very simple.
We take another vector that will hold the positions of ‘[‘.
Then we take a counter “p” that will traverse the vector.
We will maintain a count of ‘[‘ and increase ‘p’ by 1.
When we encounter a ‘]’ we decrease the count.
If it goes negative we shall start swapping.
Time Complexity O(n)
Space Complexity O(n)
Solution in C++
#include <vector> #include <algorithm> //visit www.ProDeveloperTutorial.com for 450+ solved questions #include <iostream> #include <string> #include <unordered_map> #include <queue> #include <sstream> using namespace std; long count_swaps_required(string str) { vector<int> pos; for (int i = 0; i < str.length(); ++i) { if (str[i] == '[') { pos.push_back(i); } } int count = 0; // required count number of encountered '[' int p = 0; // used to track position of next '[' in pos long result = 0; //used to store result for (int i = 0; i < str.length(); ++i) { // When '[' is encountered, // increment count and move p to next position if (str[i] == '[') { ++count; ++p; } else if (str[i] == ']') --count; if (count < 0) { result += pos[p] - i; swap(str[i], str[pos[p]]); ++p; // reset count to 1 count = 1; } } return result; } int main() { string str = "[]][]["; cout << "The number of swaps required are = " <<count_swaps_required(str) << endl; return 0; }
Output:
The number of swaps required are = 2