將給定字串轉換為 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)，因為我們使用常量空間。

在上述解決方案中，我們透過翻轉其字元將二進位制字串轉換為給定的格式，並根據陣列中給定的整數計算最小成本。程式設計師可以計算將字串轉換為給定格式的最大成本。