C++ 使用总共X个0，Y个1和Z个2计算大小为3的字符串的数量

在这个问题中，我们将计算使用给定频率创建字符串的数量，使得字符串包含相同或不同的字符。

我们有四种选项来创建使用0、1和2字符的长度为3的字符串。第一个字符串是012、000、111和222。因此，我们需要计算总共有多少这样的字符串才能得到答案。

问题陈述 - 我们给定了三个整数值：X、Y和Z。X表示0的频率，Y表示1的频率，Z表示2的频率。所给定的任务是使用0、1和2个字符创建一个长度为3的字符串，其中包含所有不同或相似的字符。因此，我们需要计算可以使用给定频率创建的这种字符串的总数。

示例示例

输入

X = 3, Y = 4, Z = 4

输出

3

解释 – 结果字符串为012，012和012。

输入

X = 1, Y = 4, Z = 4

输出

3

解释 – 结果字符串为012、111和222。

输入

X = 1, Y = 2, Z = 10

输出

4

解释 - 所得到的字符串分别为 012、222、222 和 222。

方法

我们可以注意到使用给定频率和条件可以创建四种不同的字符串。因此，如果我们说不包含不同字符的字符串不存在，答案就是 X/3 + Y/3 + Z/3。

如果存在包含不同字符的字符串，我们最多可以选择两个这样的字符串。如果我们选择三个包含不同字符的字符串，我们可以将它们转换为包含全部为1、0和2的字符串。例如，我们可以将 012、201 和 102 转换为 000、111 和 222。

因此，我们可以通过选择最多两个包含不同字符的字符串和其他包含相同字符的字符串来得到答案。

算法

步骤 1 - 定义变量 ‘cntStr’ 并将其初始化为零，用于存储字符串的计数。

步骤 2 - 使用循环从 0 到 2 执行 3 次迭代。

步骤 3 - 在循环中，如果 p 大于 X、Y 或 Z，则进入下一次迭代，因为我们无法创建包含 p 个不同字符的字符串。

步骤 4 - 从所有频率中减去 p，并将更新后的频率存储在新变量中。我们减去 p 来创建 p 个不同的字符串。

步骤 5 - 如果‘cntStr’小于 p + (freq0Left / 3) + (freq1Left / 3) + (freq2Left / 3)，则更新它的值。在这里，我们将更新后的频率除以 3 并求和，以获取具有相同字符的字符串的数量。

步骤 6 - 返回 ‘cntStr’ 的值。

示例

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

int totalStrings(int freq0, int freq1, int freq2) {
    // to store valid strings
    int cntStr = 0;
    for (int p = 0; p < 3; p++) {
        // Move to the next iteration if any frequency is smaller than p, as we can't make p strings with different characters
        if (p > freq0 || p > freq1 || p > freq2) {
            continue;
        }
        // Store the remaining characters left
        int freq0Left = freq0 - p;
        int freq1Left = freq1 - p;
        int freq2Left = freq2 - p;
        // Get the maximum number of strings
        cntStr = max(cntStr, p + (freq0Left / 3) + (freq1Left / 3) + (freq2Left / 3));
    }
    // Return the final result
    return cntStr;
}
int main(){
    int X = 3, Y = 4, Z = 4;
    cout << "The total number of maximum valid strings is " << totalStrings(X, Y, Z);
    return 0;
}

输出

The total number of maximum valid strings is 3

时间复杂度 – O(1)，因为在每种情况下只进行了3次循环迭代。

空间复杂度 – O(1)，因为我们没有使用任何额外的空间。

解决问题的另一种方法是在3个频率值中取最小值，并创建相同数量的包含不同字符的字符串。我们可以从其他2个频率中减去最小频率，并创建具有相同字符的字符串。这可能不能得到我们可以创建的最大字符串数量。因此，最好使用上述方法。