將二進位制字串分割成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’的最大絕對差值。然而，程式設計師可以使用動態規劃方法來解決這個問題。