C++ 使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’映射以存储字符串和int的对数。

步骤2 - 同样，定义’temp’字符串以存储临时字符串。

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

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

步骤5 - 在映射中增加’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对的计数使首尾字符相同。