使用总共 X 个 0、Y 个 1 和 Z 个 2，计算所有相同或不同字符组成的长度为 3 的字符串的数量

---

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

我们有四种选择可以使用字符 0、1 和 2 创建长度为 3 的字符串。第一个字符串是 012、000、111 和 222。因此，我们需要计算此类字符串的总数以获得答案。

问题陈述 – 我们给出了三个整数值：X、Y 和 Z。X 表示“0”的频率，Y 表示“1”的频率，Z 表示“Z”的频率。给定的任务是使用字符 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。

方法 1

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

如果存在包含不同字符的字符串，我们可以最多取两个此类字符串。如果我们取 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 个频率中减去最小频率，并创建一个具有相同字符的字符串。它可能无法提供我们可以创建的最大字符串。因此，最好使用上面给出的方法。