最小化后缀翻转以使二进制字符串非递减

---

在这个问题中，我们将计算通过翻转二进制字符串的字符来将字符串转换为非递减顺序所需的最小操作次数。

如果第 p 个索引处的字符为 0 且与前一个索引处的字符不匹配，我们可以翻转从第 p 个索引开始的子字符串的所有字符，并且我们可以计算最小翻转次数。

问题陈述 - 我们给定一个二进制字符串 alpha。我们需要计算将二进制字符串转换为递增顺序所需的最小翻转次数。一次翻转，我们可以选择任何索引 p 并翻转从第 p 个索引开始的子字符串。

示例

输入

alpha = "11000110"

输出

3

解释

• 我们可以在第一步翻转从第二个索引开始的子字符串。因此，结果字符串将是 11111001。

• 在第二步中，选择从第五个索引开始的字符串并翻转它。因此，字符串变为 11111110。

• 翻转最后一个字符以使字符串等于 1111111。

因此，我们需要执行总共 3 次翻转才能将字符串转换为递增顺序。

输入

alpha = "0011"

输出

0

解释 - 字符串已经是递增顺序。

输入

alpha = "1100";

输出

1

解释 - 我们可以翻转从第二个索引开始的子字符串以获得 1111 字符串。

方法一

在这种方法中，我们将遍历字符串，当我们发现当前字符为 '0' 且与前一个字符不匹配时，我们将翻转从当前索引右侧的所有字符。

算法

步骤 1 - 将 'cnt' 初始化为 0 以存储所需的最小翻转次数。

步骤 2 - 如果索引 p 和 p - 1 处的字符不相同，并且索引 'p' 处的字符为 '0'，请执行以下步骤。

步骤 3 - 从第 p 个索引开始遍历字符串。

步骤 4 - 如果第 q 个索引处的字符为 '0'，则将其替换为 '1'。否则，将其替换为 '0'。

步骤 5 - 将 cnt 值加 1。

步骤 6 - 最后，返回 'cnt' 值。

示例

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

int GetOperations(string alpha) {
   // For storing the count of operations
   int cnt = 0;
   for (int p = 1; p < alpha.length(); p++) {
     // For different adjacent characters
     if (alpha[p] != alpha[p - 1]) {
       if (alpha[p] == '0') {
         //   Flipping all bits of a substring starting from index p
         for (int q = p; q < alpha.length(); q++) {
            if (alpha[q] == '0') {
              alpha[q] = '1';
            } else {
              alpha[q] = '0';
            }
         }
         cnt++;
       }
     }
   }
   // return answer
   return cnt;
}
int main() {
   string alpha = "11000110";
   cout << "The minimum operations required to convert the string into the increasing order is " << GetOperations(alpha);
   return 0;
}

输出

The minimum operations required to convert the string into the increasing order is 3

时间复杂度 - O(N*N) 来遍历和翻转字符串字符。

空间复杂度 - O(1)，因为我们不使用任何额外空间。

方法二

在这种方法中，我们将使用布尔变量来跟踪字符串字符是否被翻转，而不是实际翻转它们。

算法

步骤 1 - 将 'cnt' 和 'isFlipped' 初始化为 '0'。

步骤 2 - 开始遍历字符串。如果索引 p 和 p - 1 处的字符不匹配，请执行以下步骤。

步骤 3 - 如果 isFlipped 等于 0，并且 alpha[p] 也为 '0'，则将 isFlipped 更改为 1，并将 'cnt' 加 1。

步骤 4 - 如果 isFlipped 为 1，则将 'cnt' 加 1。

步骤 5 - 从函数返回 'cnt'。

示例

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

int GetOperations(string alpha) {
   // For storing the count of operations
   int cnt = 0;
   // To keep track of the flip
   bool isFlipped = 0;
   for (int p = 1; p < alpha.length(); p++) {
     // For different adjacent characters
     if (alpha[p] != alpha[p - 1]) {
       // alpha[p] is '0' and its not equal to alpha[p-1]. So, the string is in decreasing order.
       if (isFlipped == 0 && alpha[p] == '0') {
         isFlipped = 1;
         cnt++;
       }
       // When a string is in increasing order, but the string is flipped
       else if (isFlipped == 1) {
         cnt++;
       }
     }
   }
   // return answer
   return cnt;
}
int main() {
   string alpha = "11000";
   cout << "The minimum operations required to convert the string into the increasing order is " << GetOperations(alpha);
   return 0;
}

输出

The minimum operations required to convert the string into the increasing order is 1

时间复杂度 - O(N) 来遍历字符串。

空间复杂度 - O(1)

在第二种方法中，我们使用布尔变量来跟踪虚拟翻转的字符。因此，它减少了每次发现字符串不是递增顺序时翻转所有右侧字符的成本。