生成具有相同数量的 01 和 10 子序列的二进制字符串

---

在这个问题中，我们将找到给定长度的二进制字符串，该字符串具有相同数量的“01”和“10”子序列。

解决该问题的朴素方法是生成给定长度的所有二进制字符串，并使用动态规划技术检查它是否包含相同数量的“10”和“01”子序列。

另一种有效的方法是根据给定长度是奇数还是偶数来准备二进制字符串。

问题陈述 - 我们给定一个大于 2 的正整数“len”。任务是找到长度为“len”的二进制字符串，该字符串包含相同数量的“10”和“01”子序列。此外，字符串应至少包含一个“1”和“0”。

示例

输入

len = 4;

输出

1001

解释 - 字符串 1001 包含两个 10 和 01 子序列。另一个答案可以是 0110。

输入

len = 5;

输出

11011

解释 - 子字符串 11011 包含两个 10 和 01 子序列。我们也可以在答案中打印 00100 字符串。

输入

len = 3;

输出

010

解释 - 答案可以是 010 和 101。

方法 1

在这种方法中，我们将使用递归函数生成给定长度的所有二进制字符串。此外，我们将使用表格动态规划来检查生成的字符串是否包含相同数量的 10 和 01 子序列。

算法

步骤 1 - 在 binStrUtil() 函数中，如果 temp 字符串的长度等于“len”，则执行 totalSubSeqs() 函数以计算给定字符串中“10”和“01”子序列的数量。

步骤 2.1 - 在 totalSubSeqs() 函数中，将“cnt”初始化为 0，并将维度为 str_len + 1 x subseq_len + 1 的“matrix”初始化为 0。

步骤 2.2 - 使用两个嵌套循环遍历矩阵。

步骤 2.3 - 如果 q 为 0，则将 matrix[p][q] 更新为 1，因为空子序列始终存在。

步骤 2.4 - 如果 p 为 0，则将 matrix[p][q] 更新为 0；长度为 0 的字符串不存在子序列。

步骤 2.3 - 在其他情况下，如果 p−1 和 q − 1 索引处的字符相同，则将 matrix[p][q] 更新为 matrix[p − 1][q− 1] + matrix[p − 1][q]，其中 matrix[p − 1][q − 1] 通过考虑当前字符来计算子序列，而 matrix[p−1][q] 在不考虑当前字符的情况下计算子序列。

步骤 2.4 - 否则，将 matrix[p][q] 更新为 matrix[p−1][q]，因为如果它们不相同，我们不需要考虑当前字符。

步骤 2.5 - 从函数返回 matrix[strLen][sub_len] 值。

步骤 3 - 如果字符串中“10”和“01”子序列相同，并且至少存在一个“1”和“0”，则将“answer”更新为“temp”字符串。

步骤 4 - 接下来，将“0”附加到 temp，并使用 binaryUtil() 函数进行递归调用。还从字符串中删除最后一个字符。

步骤 5 - 将“1”附加到“temp”字符串并进行递归调用。还从字符串中删除最后一个字符。

示例

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

string answer = "";
int totalSubSeqs(const string &temp, const string &sub) {
    int cnt = 0;
    int sub_len = sub.length();
    int strLen = temp.length();
    int matrix[strLen + 1][sub_len + 1] = {0};
    // Fill the matrix
    for (int p = 0; p <= strLen; p++) {
        for (int q = 0; q <= sub_len; q++) {
            // Base cases
            if (q == 0) {
                matrix[p][q] = 1;
            } else if (p == 0) {
                // For strings with length 0.
                matrix[p][q] = 0;
            } else {
                // When characters are the same
                if (temp[p - 1] == sub[q - 1]) {
                    matrix[p][q] = matrix[p - 1][q - 1] + matrix[p - 1][q];
                } else {
                    matrix[p][q] = matrix[p - 1][q];
                }
            }
        }
    }
    cnt = matrix[strLen][sub_len];
    return cnt;
}
void binStrUtil(string &temp, int len) {
    if (temp.length() == len) {
        // New binary string found
        // If cnt of 10 and 01 subsequences are the same, choose it as the answer
        if (totalSubSeqs(temp, "10") == totalSubSeqs(temp, "01")) {
            if (count(temp.begin(), temp.end(), '1') > 0 && count(temp.begin(), temp.end(), '0') > 0)
                answer = temp;
        }
        return;
    }
    // Insert 0 and backtrack
    temp += '0';
    binStrUtil(temp, len);
    temp.pop_back();
    // Insert 1 at the current index and backtrack
    temp += '1';
    binStrUtil(temp, len);
    temp.pop_back();
}
int main() {
    int len = 4;
    string temp;
    binStrUtil(temp, len);
    cout << "The binary string of the given length and following the given condition is: " << answer << endl;
    return 0;
}

输出

The binary string of the given length and following the given condition is: 1001

时间复杂度 - O(N*2N)，其中 O(N) 用于查找字符串中 10 和 01 子序列的总数，而 O(2N) 用于查找所有二进制字符串。

空间复杂度 - 用于 matrix[] 数组和存储二进制字符串的 O(N)。

方法 2

对于二进制字符串的偶数长度，如果我们将“1”放在 len/2 和 len/2 − 1 索引处，并将“0”放在其他索引处，我们可以得到具有相等 01 和 10 子序列的二进制字符串。

对于二进制字符串的奇数长度，如果我们将“1”放在 len/2 索引处，并将“0”放在其他索引处，我们可以得到给定长度的所需二进制字符串。

算法

步骤 1 - 初始化“temp”字符串和“middle”为“len/2”。

步骤 2 - 如果长度为偶数，请执行以下步骤。

步骤 2.1 - 进行等于给定“len”的迭代。如果当前索引等于中间或中间 – 1，则将“1”附加到 temp 字符串。否则，将“0”附加到“temp”字符串。

步骤 3 - 如果给定长度为奇数，请执行以下步骤。

步骤 3.1 - 进行等于给定“len”的迭代。如果当前索引等于中间，则将“1”附加到“temp”字符串。否则，将“0”附加到“temp”字符串。

步骤 4 - 返回“temp”字符串。

示例

#include <iostream>
using namespace std;

string getBinStr(int len) {
    string temp = "";
    // Get middle of the length
    int middle = len / 2;
    // For even length
    if (len % 2 == 0) {
        for (int p = 0; p < len; p++) {
            // Place two 1's at the middle
            if (p == middle || p == middle - 1) {
                temp += "1";
            } else {
                // Place 0's at the remaining places
                temp += "0";
            }
        }
        // Return the final binary string
        return temp;
    }
    // For odd length
    else {
        for (int p = 0; p < len; p++) {
            // Insert '1' at middle index
            if (p == middle) {
                temp += "1";
            } else {
                // Insert '0' at other indexes
                temp += "0";
            }
        }
        // Return the final binary string
        return temp;
    }
}
int main() {
    int len = 5;
    cout << "The binary string of the given length and following the given condition is " << getBinStr(len) << endl;
    return 0;
}

输出

The binary string of the given length and following the given condition is 00100

时间复杂度 - O(len) 用于生成给定长度的二进制字符串。

空间复杂度 - O(len) 用于存储二进制字符串。

第二种方法基于观察，它比第一种方法效率高得多。在第二种方法中，我们也可以在中间索引处打印“0”，在其他索引处打印“1”。