将二进制字符串分割成K个不相交子序列，以最小化0和1的最大频率差

---

在这个问题中，我们将给定的二进制字符串分割成K个子序列，使我们能够最小化给定字符串中‘1’和‘0’计数的最大绝对差值。

解决这个问题的逻辑是在子序列中创建0和1的最大对数。这样，我们可以得到每个子序列之间的最小差值。

问题陈述 − 我们给定一个长度为N的二进制字符串bin_str。我们还给定了正整数K。我们需要将给定的字符串分割成K个不相交的子序列，以最小化每个子序列中‘0’和‘1’计数的最大绝对差值。也可以使用空子序列。在输出中，打印最小差值。

注意 − 我们可以使用给定字符串的非相邻字符创建不相交的子序列。

示例

输入

bin_str = "110011", K = 3

输出

1

解释 − 我们可以将字符串分割成‘10’，‘11’和‘01’子序列，因为我们需要取不相交的子序列。

在每个子序列中，‘1’和‘0’的数量差为{1, 2, 1}。因此，最大差值为2 - 1 = 1。

输入

K = 2;   string bin_str = "111011";

输出

2

解释 − 2个不相交的子序列可以是[‘111’，‘101’]。因此，每个子序列中‘1’和‘0’的数量差为{3, 1}。最大绝对差值为2。

方法一

如果我们可以将所有子序列之间的总差值平均分配，那么我们可以得到所有子序列之间的最小差值。因此，我们需要找到给定字符串中‘0’和‘1’的数量差值。之后，我们可以将差值除以给定的K，并取其上舍入值作为答案。

算法

步骤1 − 初始化‘cnt0’和‘cnt1’以存储给定字符串中‘0’和‘1’的计数。

步骤2 − 遍历给定的二进制字符串。如果当前字符是‘0’，则将‘cnt0’加1。否则，将‘cnt1’加1。

步骤3 − 获取‘cnt1’和‘cnt0’之间的绝对差值。

步骤4 − 将差值除以K后返回其上舍入值。

示例

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

int getMinDiff(string bin_str, int str_len, int K) {
    int cnt0 = 0, cnt1 = 0;
    // Count 0 and 1 in the binary string
    for (int p = 0; p < str_len; ++p) {
        if (bin_str[p] == '0')
            cnt0++;
        else
            cnt1++;
    }
    // Get the absolute difference between 0 and 1 count
    int difference = abs(cnt1 - cnt0);
    // Get ceil of difference and return it
    return (difference + K - 1) / K;
}
int main() {
    int K = 3;
    string bin_str = "110011";
    int str_len = bin_str.length();
    cout << "The absolute minimum difference after dividing the binary string into K substrings is " << getMinDiff(bin_str, str_len, K) << endl;
    return 0;
}

输出

The absolute minimum difference after dividing the binary string into K substrings is 1

时间复杂度 − O(N)，用于计算二进制字符串中‘1’和‘0’的数量。

空间复杂度 − O(1)

我们学习了如何将给定的字符串分割成K个不相交的子序列，以最小化给定子序列中‘1’和‘0’的最大绝对差值。然而，程序员可以使用动态规划方法来解决这个问题。