C++ 将给定的字符串转换为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

解释 – 字符串已经在要求的格式中。

方法

我们可以观察到，根据给定条件，创建二进制字符串只有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

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

空间复杂度 - 使用常数空间，空间复杂度为O(1)。

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