最小化從開頭或結尾移除字元以使二進位制字串平衡

---

在這個問題中，我們將列印我們需要從開頭和結尾移除的最小字元數，以使給定字串中 '1' 和 '0' 的數量相同。

如果我們找到 '1' 和 '0' 數量相同的最大子字串，我們可以透過從給定字串的長度中減去子字串的長度來得到答案。我們將使用字首和技術來找到具有相同數量 '1' 和 '0' 的最大子字串。

問題陳述 − 我們給定了一個包含 N 個字元的二進位制字串 'bin_str'。我們需要從開頭和結尾移除一些字元，以使 '1' 和 '0' 的數量相等。

示例

輸入

bin_str = "0011001"

輸出

1

解釋 − 我們可以移除第一個 '0' 以使給定字串中 '1' 和 '0' 的數量相等。

輸入

bin_str = "111000";

輸出

0

解釋 − 字串已經包含相同數量的 '1' 和 '0'。因此，我們不需要從開頭或結尾移除任何字元。

輸入

bin_str = "00000";

輸出

5

解釋 − 字串包含零個 '1'。因此，我們需要移除給定字串的所有字元。

方法 1

在這種方法中，我們將找到給定二進位制字串中具有相同數量 '1' 和 '0' 的最大子字串。

為了簡化解決方案程式碼，我們將 '0' 視為 -1，'1' 視為 1。之後，我們將使用字首和技術來找到字首和等於零的最大子字串，這與具有相同數量 '1' 和 '0' 的最大子字串相同。

演算法

步驟 1 − 定義 'prefmap' 來儲存字首和以及它出現的位置。

步驟 2 − 將 'prefsum' 初始化為 0 以跟蹤字首和，並將 'ans' 初始化為儲存子字串的最大長度。

步驟 3 − 遍歷二進位制字串。如果當前字元是 '0'，則將 -1 新增到 'prefSum'。否則，將 '1' 新增到 'prefSum'。

步驟 4 − 如果 'prefSum' 值為 0，則如果當前索引 + 1 大於 'ans' 值，則更新 'ans' 值。

步驟 5 − 如果 'prefSum' 值已經存在於 map 中作為鍵，則從當前索引中減去它的值，如果結果值大於 'ans' 值，則更新它。

步驟 6 − 將當前 'prefSum' 插入到 map 中，並將當前索引作為值。

步驟 7 − 最後，在從二進位制字串的長度中減去 'ans' 後返回結果值。

示例

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

int countRemoval(string bin_str) {
    // To store prefix sum index
    unordered_map<int, int> prefMap;
    int bin_len = bin_str.size();
    // To store prefix sum
    int prefSum = 0;
    // To store the length of the longest binary string having equal 0's and 1's
    int ans = 0;
    for (int p = 0; p < bin_len; p++) {
        // Update prefix sum according to '1' and '0'
        prefSum += ((bin_str[p] == '1') ? 1 : -1);
        // When binary strings have equal '0' and '1'.
        if (prefSum == 0) {
            ans = max(ans, p + 1);
        }
        // Find sum in the map
        if (prefMap.count(prefSum)) {
            // prefMap[prefSum] is the first index where the same prefix sum occurred. We can take the middle string as a valid string.
            ans = max(ans, p - prefMap[prefSum]);
        } else {
            // Update prefix sum
            prefMap[prefSum] = p;
        }
    }
    // Number of characters to remove from start and end
    return bin_len - ans;
}
int main() {
    string bin_str = "0011001";
    cout << "The number of removals required to make 1's and 0's equal is " << countRemoval(bin_str) << endl;
    return 0;
}

輸出

The number of removals required to make 1's and 0's equal is 1

時間複雜度 − O(N) 用於查詢具有相同數量 '0' 和 '1' 的最大字串。

空間複雜度 − O(N) 用於在 map 中儲存字首和值。

我們使用了相同的演算法來查詢和為 0 的最大子字串來解決問題。程式設計師可以使用蠻力方法來解決問題，在該方法中，我們可以從開頭或結尾移除每個字元以檢查字串是否包含相同數量的 '1' 和 '0'。