C++ 将至多一个0替换为1来最大化”10″子序列

在这个问题中，我们需要通过将0或1的’0’字符替换为’1’来最大化给定二进制字符串中的”10″子序列。

我们可以依次将每个’0’替换为’1’，并找到更新后的字符串中的最大”10″子序列数量。

问题陈述

我们有一个名为str1的二进制字符串，其中只包含0和1字符。我们最多可以将一个’0’替换为’1’，并需要找到给定字符串中最大数量的”10″子序列。

示例示例

输入

str1 = "10110"

输出

4

解释

字符串 “10110” 中只包含3个连续子串 “10”，分别在索引位置 {0, 1}，{2, 4} 和 {3, 4}。

当我们将第一个索引位置的字符 “0” 替换成 “1”，得到字符串 “11110”，其中有4个连续子串 “10”，分别在索引位置 {0, 4}，{1, 4}，{2, 4} 和 {3, 4}。

输入

str1 = ‘110’

输出

2

说明

字符串已经包含了2个’10’子序列，所以我们不需要用’1’替换任何’0’。

输入

str1 = "011010";

输出

7

解释

初始子字符串包含在索引{1,3},{2,3},{1,5},{2,5}和{4,5}处的5个’10’子字符串。

替换第0个索引处的’0’后，我们在{0,3},{1,3},{2,3},{0,5},{1,5},{2,5}和{4,5}处得到7个’10’子字符串。

如果我们替换第3个索引处的’0’，我们得到4个’10’子字符串。

如果我们替换第5个索引处的’0’，我们得到2个’10’子字符串。

因此，我们选择了第一个’0’，因为它在给定的二进制字符串中创建了最大的’10’子字符串。

方法1

当我们将任何’0’替换为’1’时，我们会得到一些新的子字符串，并且会失去一些先前使用被替换’0’形成的子字符串。

当我们用’1’替换’0’时，新形成的’10’子字符串的数量与后缀0的数量相同，并且失去的子字符串是前缀0的数量。

为了解决这个问题，我们将准备一个前缀1和后缀0的数组，并取后缀0和前缀1的最大减法值，这些值是新形成的子字符串。

算法

• 第一步 - 定义’suffixZeros’列表来存储二进制字符串中每个字符的后缀0的数量。同时，如果字符串的最后一个字符是’0’，将列表的最后一个元素初始化为1；否则，初始化为0。

• 第二步 - 以逆向顺序遍历字符串，并根据当前元素是否为0，将前一个元素的后缀0的总和存储在其后面。

• 第三步 - 同样，定义’prefixOnes’列表来存储每个字符串索引处的前缀’1’的总数。同时，根据字符串的第一个字符是1还是0，将列表的第一个元素初始化为1或0。

• 第四步 - 开始遍历字符串，并根据当前元素是1还是0，将前一个元素的前缀1的总和与1或0相加，存储在当前前缀值中。

• 第5步 - 接下来，我们需要计算给定字符串中的初始10子序列。

• 第5.1步 - 遍历字符串时，如果遇到1，我们需要将后面的零添加到initialPairs变量中，因为1可以与后面的所有零形成10子序列。

• 第6步 - 接下来，我们需要计算替换0为1后添加的总子序列数。

• 第6.1步 - 遍历字符串，如果第p个字符是0，按照以下步骤操作。

• 第6.2步 - 如果p等于字符串长度减1，则将add变量更新为0，因为当我们更新最后一个0时，无法再形成新的10子序列。

• 步骤 6.3 – 否则，在下一个索引上，使用后缀零更新“add”变量的值。

• 步骤 6.4 – 如果p等于0，则将“remove”更新为0，因为当我们将第一个索引处的“0”替换为“1”时，不会影响其他子序列。

• 步骤 6.5 – 否则，在前一个索引上，使用前缀1进行初始化“remove”。

• 步骤 6.6 – 在“addPairs”存储区中，add减去remove值为净增加的子序列。

• 步骤 6.7 – 如果“addPairs”值是最大的话，用“addParis”值更新“newPairs”变量的值。

• 步骤 7 返回初始对和添加对的总和。

示例

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

int maxSubSeq(string str) {
   int str_len = str.length();
   // To store suffix zeros
   vector<int> suffixZeros(str_len + 1);

   // Checking if its value is 0
   suffixZeros[str_len - 1] = str[str_len - 1] == '0';
   for (int p = str_len - 2; p >= 0; p--) {
      suffixZeros[p] = suffixZeros[p + 1] + (str[p] == '0');
   }

   // To store prefix ones
   vector<int> prefixOnes(str_len);

   // Initializing prefixOnes[0]
   prefixOnes[0] = (str[0] == '1');

   // Coutning prefix ones
   for (int p = 1; p < str_len; p++) {
      prefixOnes[p] = prefixOnes[p - 1] + (str[p] == '1');
   }
   int initialPairs = 0;
   for (int p = 0; p < str_len; p++) {
      if (str[p] == '1')

      // Calculating initial pairs. '1' can form the subsequence '10' with all suffix zeros.
      initialPairs += suffixZeros[p + 1];
   }

   // New pairs
   int newPairs = 0;
   int add = 0, remove = 0;

   // Traverse the string
   for (int p = 0; p < str_len; p++) {

      // As we need to replace '0' and find the maximum subsequences
      if (str[p] == '0') {
         if (p == str_len - 1) {
            add = 0;
         } else {
            add = suffixZeros[p + 1];
         } 
         if (p == 0) {
            remove = 0;
         } else {
            remove = prefixOnes[p - 1];
         }
         // Total added pairs
         int addPairs = add - remove;
         // Finding maximum new pairs
         newPairs = max(newPairs, addPairs);
      }
   }

   // Maximum final pairs
   return initialPairs + newPairs;
}
int main(){
   string str1 = "10110";
   cout << "The maximum subsequences we can form by replacing the 0 with 1 is - " << maxSubSeq(str1);
   return 0;
}

输出

The maximum subsequences we can form by replacing the 0 with 1 is - 4

时间复杂度 – O(N) 用于计算后缀零、前缀一和在最多替换0为1的情况下找到最大的10子序列。

空间复杂度 – O(N) 用于存储前缀为1和后缀为0的情况。

通过解决上述问题，程序员学会了找到前缀数组和后缀数组。同时，我们学会了通过尝试和替换每个0为1来得到输出，在给定字符串中找到最大的10子序列。