C++ 在K个步骤中通过对子字符串执行异或操作来最大化二进制字符串的值

在这个问题中，我们将通过对给定二进制字符串的子字符串执行K个异或操作来最大化二进制字符串的值。

为了最大化任何二进制字符串，我们应该最大化从最左边的零开始的子字符串。例如，为了最大化’11001’字符串，我们需要选择另一个子字符串，以便最大化’001’子字符串。

问题描述 - 我们给出了一个名为bin_str的二进制字符串，其中包含N个字符。我们需要通过对任意两个子字符串进行异或操作来在K个操作中最大化二进制字符串的值。已知子字符串可以是相同的、相交的或非相交的。

示例示例

输入

bin_str = "1101"; K = 1;

输出

1111

解释

我们可以取10和1101子字符串，当我们对两者执行XOR运算时，我们得到1111最大字符串。

输入

bin_str = "110101"; K = 2

输出

111110

解释

• 在第一次操作中，我们取出了110101和1010两个子串。当我们对这两个子串进行XOR操作时，得到了111111的二进制字符串。

• 在第二次操作中，我们取出了111111和1这两个子串。当我们对这两个子串进行XOR操作时，得到了111110，这是我们能够得到的最大字符串。

  输入

bin_str = "01"; K = 1;

输出

1

解释：

获取01和0子字符串以生成1。

方法1

在这个方法中，我们将从最左边的0到结尾取一个子字符串，并找到字符串的另一个子字符串以获取最大的二进制字符串值。

例如，二进制字符串是1110010101。为了最大化二进制字符串，我们需要最大化0010101子字符串。因此，我们将二进制字符串本身作为一个子字符串，另一个长度相同的字符串‘0010101’一起使用，以最大化二进制字符串。

算法：

• 第一步 - 执行maxValUtil()函数K次，并使用其返回值更新二进制字符串。

• 第二步 - 在maxValUtil()函数中，将”leftZero”初始化为-1，用于存储最左侧零的索引，将”cnt0″和”cnt1″初始化为0，用于分别存储二进制字符串中0和1的计数。

• 第三步 - 遍历字符串，如果当前字符为”1″，则将”cnt1″加1。否则，如果”leftZero”为-1，则更新其值为当前索引并将”cnt0″值加1。

• 第四步 - 如果”cnt1″和”len”相等，则对二进制字符串与”1″进行异或操作，并返回其值。

• 第四步.1

• 步骤4.1.1 − 在addZero()函数中，在字符串的开头添加所需的零。

• 步骤4.2 − 初始化“XOR”字符串，以存储执行两个字符串的XOR操作后的结果。

• 步骤4.3 − 遍历两个字符串，如果两个字符串中的第p个索引处的字符相同，则将“0”附加到XOR字符串。否则，将“1”附加到XOR字符串。

• 步骤4.4 − 返回XOR字符串。

• 步骤5 - 在 maxValUtil() 函数中，如果 cnt0 等于二进制字符串的长度，则返回 0。

• 步骤 6 - 使用 substr() 方法从 leftZero 索引开始，将子字符串赋值给 rightStr 字符串。并且，将 size 初始化为 rightStr 字符串的长度，temp 初始化为 rightStr 字符串，maxRes、temp1 和 temp2 初始化为空字符串。

• 步骤 7 - 开始遍历二进制字符串。如果索引小于 size 变量的值，则将一个字符追加到 temp1 字符串中。

• 步骤 8 - 否则，获取 temp 和 temp1 字符串的 XOR 值。如果 XOR 值超过 maxRes 字符串的值，则将 maxRes 更新为 res，将 temp2 更新为 temp1。同时，从 temp1 字符串中移除第一个字符，并将当前字符追加到末尾。

这里，我们找到子字符串 ‘temp2’，使得 ‘temp1’ 与 ‘temp2’ 的异或最大化以最大化二进制字符串。

• 步骤 9 − 处理最后一种情况，其中我们将 temp1 字符串与 rightStr 字符串进行异或运算。

• 步骤 10 − 接下来，对二进制字符串和 temp2 字符串进行异或运算，并将结果存储在 answer 中。

• 步骤 11 − 在去除前导零后，返回 ‘answer’ 字符串。

示例

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

void addNZero(string &substr, int n) {
   // Adding the initial '0' to the string to make its length the same as the other sub string
   for (int p = 0; p < n; p++) {
      substr = "0" + substr;
   }
}

// Finding XOR of two strings
string getXOR(string temp1, string temp2) {  

   // Get string sizes
   int temp1_len = temp1.length();
   int temp2_len = temp2.length();

   // Append zeros to the smaller string
   if (temp1_len > temp2_len) {
      addNZero(temp2, temp1_len - temp2_len);
   } else if (temp2_len > temp1_len) {
      addNZero(temp1, temp2_len - temp1_len);
   }

   // Final string length
   int len = max(temp1_len, temp2_len);

   // To store the resultant XOR
   string XOR = "";

   // Take XOR of both strings
   for (int p = 0; p < len; p++) {
      if (temp1[p] == temp2[p])
         XOR += "0";
      else
         XOR += "1";
   }
   return XOR;
}
string maxValUtil(string bin_str) {

   // String length
   int len = bin_str.size();
   int leftZero = -1, cnt0 = 0, cnt1 = 0;

   // Calculate number of 0's and 1's in the given string.
   for (int p = 0; p < len; p++) {
      if (bin_str[p] == '1') {
         cnt1++;
      } else {

         // For the left most '0'
         if (leftZero == -1) {
            leftZero = p;
         }
         cnt0++;
      }
   }

   // Case 1 - When the string contains all 1's
   if (cnt1 == len) {
      return getXOR(bin_str, "1");
   }

   // Case 2 - When the string contains all zeros
   if (cnt0 == len) {
      return "0";
   }

   // Take the substring starting from left most '0' as we need to maximize it
   string rightStr = bin_str.substr(leftZero, len - leftZero);
   int size = rightStr.size();
   string temp = rightStr;
   string maxRes = "";
   string temp1 = "", temp2 = "";

   // Choosing the second string
   for (int q = 0; q < len; q++) {

      // Finding the substring of length 'size' from start
      if (q < size) {
      temp1 += bin_str[q];
      } else {

         // If temp1 gives the maximum XOR result, choose it as a second string
         string res = getXOR(temp, temp1);
         if (res > maxRes) {
            maxRes = res;
            temp2 = temp1;
         }

         // Update temp1 string
         temp1 = temp1.substr(1);
         temp1 += bin_str[q];
      }
   }

   // Handling the last case
   string res = getXOR(temp1, temp);
   if (res > maxRes) {
      maxRes = res;
      temp2 = rightStr;
   }

   // Take the XOR of the original string and the second string
   string answer = getXOR(bin_str, temp2);
   leftZero = -1;
   for (int p = 0; p < answer.size(); p++) {

      // Remove initial zeros
      if (answer[p] != '0') {
         leftZero = p;
         break;
      }
   }
   if (leftZero == -1) {
      return "0";
   }

   // Final maximum string
   return answer.substr(leftZero);
}
string findMaxValue(string bin_str, int K) {

   // Find the maximum value of the updated binary string
   for (int p = 0; p < K; p++) {
      bin_str = maxValUtil(bin_str);
   }
   return bin_str;
}
int main() {
   string bin_str = "1101";
   int K = 1;
   cout << "The maximum value of the string after performing " << K << " XOR operations is - " << findMaxValue(bin_str, K) << endl;
   return 0;
}

输出

The maximum value of the string after performing 1 XOR operations is - 1111

时间复杂度 – O(NNK)，其中O(N)用于找到最大化二进制字符串的子字符串，另一个O(N)用于执行两个字符串的XOR操作，O(K)用于执行总共K次操作。

空间复杂度 – O(N)用于存储临时字符串。