最小化比特替换次数，使01子串计数等于10子串计数

---

问题陈述 - 我们给定长度为 N 的二进制字符串。我们需要找到使二进制字符串平衡所需的最小翻转字符数。翻转字符意味着将 0 转换为 1，将 1 转换为 0。如果任何字符串包含相同数量的“01”和“10”对，我们可以说该字符串是平衡的二进制字符串。

示例

输入

str = "001010"

输出

0

解释 - 字符串包含 2 个“01”和“10”对。因此，我们不需要执行任何翻转操作。

输入

 str = ‘00001’

输出

1

解释 - 字符串包含 1 个“01”对，但不包含“10”对，因此我们需要执行 1 次翻转操作。

输入

 str = ‘1’

输出

0

解释 - 输入字符串已经平衡。

观察 - 我们可以注意到，如果字符串的第一个和最后一个字符相等，则二进制字符串始终包含相同数量的 01 和 10 对。

让我们看看下面的例子。

• 1 - 字符串是平衡的，因为第一个和最后一个字符相同。

• 0 - 平衡字符串。

• 10 - 第一个和最后一个字符不同，因此字符串不平衡。

• 101 - 平衡字符串。

• 010 - 平衡字符串。

• 1111 - 平衡字符串。

• 01010 - 平衡字符串。

• 0101 - 不平衡字符串。

方法 1

在这种方法中，我们将使用 map 数据结构来存储给定字符串的“01”和“10”对的总数。之后，我们可以取对数之间的差值以找到最小翻转次数。

算法

步骤 1 - 定义“count”map 来存储字符串和 int 的对。

步骤 2 - 此外，定义“temp”字符串来存储临时字符串。

步骤 3 - 遍历字符串直到倒数第二个索引。

步骤 4 - 在 temp 字符串中，存储从第 p 个索引开始长度为 2 的子字符串。

步骤 5 - 在 map 中增加“temp”字符串的计数。

步骤 6 - 取 count[01] 和 count[10] 之间的绝对差值并返回其值。

示例

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

int totalReplacement(string alpha) {
    unordered_map<string, int> count;
    string temp;
    // count the number of occurrences of 01 and 10
    for (int p = 0; p < alpha.length() - 1; p++) {
        // substring of length 2 starting from index p
        temp = alpha.substr(p, 2);
        // Increase the count of temp by 1
        count[temp]++;
    }
    // return the absolute difference between the count of 01 and 10
    return abs(count["10"] - count["01"]);
}
int main() {
    string str = "001010";
    cout << "The total number of replacements required to make tota 01 equal to 10 is: " << totalReplacement(str) << endl;
    return 0;
}

输出

The total number of replacements required to make tota 01 equal to 10 is: 0

时间复杂度 - O(N)，因为我们迭代字符串。

空间复杂度 - O(2) ~ O(1)，因为我们使用 map。

方法 2

在这种方法中，我们将使用计数变量来存储字符串的 01 和 10 对的计数，而不是使用 map。它提高了代码的空间复杂度。

算法

步骤 1 - 定义“temp”字符串，并将“count01”和“count10”变量初始化为零。

步骤 2 - 使用 for 循环遍历字符串。

步骤 3 - 获取长度为 2 的子字符串。

步骤 4 - 如果 temp 等于“01”，则将“count01”的值增加 1。否则，将“count10”的值增加 1。

步骤 5 - 返回 count01 和 count10 之间的绝对差值。

示例

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

int totalReplacement(string alpha) {
    string temp;
    int cnt01 = 0, cnt10 = 0;
    // count the number of occurrences of 01 and 10
    for (int p = 0; p < alpha.length() - 1; p++) {
        // substring of length 2 starting from index p
        temp = alpha.substr(p, 2);
        if (temp == "01") {
            cnt01++;
        } else {
            cnt10++;
        }
    }
    // return the absolute difference between the count of 01 and 10
    return abs(cnt01 - cnt10);
}
int main() {
    string str = "010101010101";
    cout << "The total number of replacements required to make tota 01 equal to 10 is: " << totalReplacement(str) << endl;
    return 0;
}

输出

The total number of replacements required to make tota 01 equal to 10 is: 1

时间复杂度 - O(N)，因为我们迭代字符串。

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

对于任何给定的二进制字符串，我们将在输出中得到 0 或 1，因为根据 01 和 10 对的计数，我们需要使第一个和最后一个字符相同。