最小化从开头或结尾移除字符以使二进制字符串平衡

---

在这个问题中，我们将打印我们需要从开头和结尾移除的最小字符数，以使给定字符串中 '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'。