使用總共 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 個頻率中減去最小頻率，並建立一個具有相同字元的字串。它可能無法提供我們可以建立的最大字串。因此，最好使用上面給出的方法。