最小化位元替換次數，使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 對的計數，我們需要使第一個和最後一個字元相同。