将给定字符串转换为 XYXY… 或 XXYY… 类型，并最小化转换成本。

---

在这个问题中，我们需要将给定的二进制字符串转换为 abababab 或 aabbaabb 格式，并找到该格式的最小成本。此外，我们还在操作数组中给出了翻转任何字符的成本。

问题陈述 - 我们给定了一个二进制字符串 bin_str 和一个包含正整数的操作数组。字符串和数组的大小相同且为偶数。任务是找到将字符串转换为 ababab… 或 aabbaabb… 格式的最小成本。在给定字符串中翻转任何字符的成本是在操作数组中第 i 个索引处的数值。

示例

输入

bin_Str = "1001", operations[] = {1, 3, 2, 3}

输出

3

解释

• 将字符串转换为 1010，成本为 2 + 3 = 5，因为我们需要翻转最后两位。

• 将字符串转换为 0101，成本为 1 + 3 = 4，因为我们需要翻转前两位。

• 对于 1100 字符串，成本为 3 + 3 = 6。

• 对于 0011，成本为 1 + 2 = 3

因此，最小成本为 3。

输入

bin_Str = "11001100", operations[] = {1, 3, 2, 3, 2, 3, 4, 2}

输出

0

解释 - 字符串已处于所需格式。

输入

bin_Str = "01010101010101", operations[] = {1, 3, 2, 3, 2, 3, 4, 2}

输出

0

解释 - 字符串已处于所需格式。

方法 1

我们可以观察到，根据给定的条件，只有 4 种可能的方式来创建二进制字符串。

• 01010101010101….

• 1010101010101010…..

• 001100110011001100…

• 1100110011001100…

我们可以尝试将字符串转换为所有可能的组合并计算成本。之后，我们可以将最小成本作为问题的答案。

算法

步骤 1 - 如果字符串长度为 2，则返回 0，因为它始终处于给定格式。

步骤 2 - 通过将字符串格式作为参数传递来执行 helper() 函数。

步骤 3 - 在 helper() 函数中，将 'cnt' 变量初始化为 0 以存储成本。

步骤 4 - 开始遍历字符串。如果第 p 个索引处的字符不等于 'a'，则将 operations[p] 添加到 'cnt' 中，因为我们需要翻转字符。

步骤 5 - 如果第 p + 1、p + 2 和 p + 3 个索引处的字符与 b、c 和 d 字符不同，则将其成本添加到 'cnt' 中。

步骤 6 - 从 helper() 函数返回 'cnt' 值。

步骤 7 - 在 totalOperations() 函数中，获取将字符串转换为每四种格式的成本。

步骤 8 - 之后，从 x、y、z 和 w 中返回最小值。

示例

#include <bits/stdc++.h>
using namespace std;

int helper(string bin_Str, int operations[], char a, char b, char c, char 
d) {
   int cnt = 0;
   // Traverse the string
   for (int p = 0; p < bin_Str.length(); p += 4) {
      // Count the cost to convert the string to the required form
      if (bin_Str[p] != a)
         cnt += operations[p];
      if (p + 1 < bin_Str.length() && bin_Str[p + 1] != b)
         cnt += operations[p + 1];
      if (p + 2 < bin_Str.length() && bin_Str[p + 2] != c)
         cnt += operations[p + 2];
      if (p + 3 < bin_Str.length() && bin_Str[p + 3] != d)
         cnt += operations[p + 3];
   }
   return cnt;
}
int totalOperations(int op_len, string bin_Str, int operations[]) {
   // For the string of length 2
   if (bin_Str.length() == 2) {
      return 0;
   }
   // For the strings of length 4 or more
   int x = helper(bin_Str, operations, '0', '1', '0', '1');
   int y = helper(bin_Str, operations, '1', '0', '1', '0');
   int z = helper(bin_Str, operations, '1', '1', '0', '0');
   int w = helper(bin_Str, operations, '0', '0', '1', '1');
   return min({x, y, z, w});
}
int main() {
   int op_len = 4;
   string bin_Str = "1001";
   int operations[] = {1, 3, 2, 3};
   cout << "The minimum operations required to update the binary string is " << totalOperations(op_len, bin_Str, operations) << "\n";
   return 0;
}

输出

The minimum operations required to update the binary string is 3

时间复杂度 - O(N) 以在 helper() 函数中遍历字符串。

空间复杂度 - O(1)，因为我们使用常量空间。

在上述解决方案中，我们通过翻转其字符将二进制字符串转换为给定的格式，并根据数组中给定的整数计算最小成本。程序员可以计算将字符串转换为给定格式的最大成本。