Sponsored
Sponsored
This approach involves traversing the string and counting the balance between opening and closing brackets. You increase a count when you find an opening bracket and decrease the count when you find a closing bracket. If at any point the count goes negative, a swap is needed to balance out the string, and the swap count is incremented. The final swap count will be the required number of swaps to make the string balanced.
Time Complexity: O(n), where n is the length of string s.
Space Complexity: O(1), as no extra space is used aside from a few variables.
1#include <iostream>
2#include <string>
3
4int minSwaps(const std::string &s) {
5 int balance = 0, swaps = 0;
6
7 for (char ch : s) {
8 balance += (ch == '[') ? 1 : -1;
9
10 if (balance < 0) {
11 swaps++;
12 balance += 2;
13 }
14 }
15 return swaps;
16}
17
18int main() {
19 std::string s = "][][";
20 std::cout << "Minimum swaps: " << minSwaps(s) << std::endl;
21 return 0;
22}The C++ solution follows a similar logic as the C solution but uses the modern range-based for loop for iterating through the string. It calculates the required swaps by maintaining the balance of brackets.
This approach uses two pointers to traverse the string efficiently. One pointer starts from the beginning of the string, and the other starts at the end. Using these pointers, swaps are performed when an excessive number of closing brackets on one side can be paired with an opening bracket on the other side.
Time Complexity: O(n), where n is the length of string s, due to traversing the string once.
Space Complexity: O(1), as we're only using constants amount of space for pointers and variables.
public class MinSwaps {
public static int MinSwapsToBalance(string s) {
int left = 0, right = s.Length - 1, swaps = 0;
while (left < right) {
if (s[left] == '[') {
left++;
} else if (s[right] == ']') {
right--;
} else {
swaps++;
left++;
right--;
}
}
return swaps;
}
public static void Main(string[] args) {
string s = "][][";
Console.WriteLine("Minimum swaps: " + MinSwapsToBalance(s));
}
}C# method relies on two moving pointers that progress towards each other, handling mismatches effectively by swapping relevant indices, achieving a balanced result in minimum moves.