使用給定字元構成至少包含兩個不同字元的長度為 3 的字串的個數

---

給定三個整數 'a'、'b' 和 'c'，分別表示三個不同字元 'A'、'B' 和 'C' 的頻率。我們需要找到使用這些字元可以形成的不同字串的數量，並且形成的字串中必須至少存在兩個不同的字元。我們將看到解決此問題的兩種方法，一種是樸素方法，另一種是數學方法。

示例

Input 1: a = 3, b = 2, c = 4 

Output:  3 

解釋

我們可以建立三個字串 'ABC'、'ABC' 和 'ACC'。在這些字串中，我們使用了 'A' 3 次、'B' 2 次和 'C' 4 次，這與或小於它們的給定頻率，並且所有字串都包含至少兩個不同的字元。

Input 2: a = 1, b = 3, c = 10

Output: 4

解釋

我們可以建立字串 'ACC'、'BCC'、'BCC' 和 'BCC'。我們使用了所有給定的字元，除了兩個 'C'，因為沒有其他字元可以用來建立新的字串。如果我們嘗試其他組合，那麼最終字串的數量將更少。

樸素方法

樸素方法是找到所有可能的組合，並使用給定的頻率，但問題是它將花費大量的時間複雜度，並且效率非常低。

我們需要生成所有可能的子字串，如果數字很大，那麼這將花費大量的時間和空間，而電腦無法處理。

數學方法

思路

這種方法背後的思路是，我們需要字串中至少有兩個不同的字元，因此我們將始終嘗試關注頻率最低的字元。

我們可以建立的最大字串數量是 (a+b+c)/3，並且可能的結果僅取決於頻率最低的兩個字元。

假設，如果頻率最低的兩個字元是 x 和 y，並且它們的和大於或等於 (a+b+c)/3，那麼我們可以列印此值作為答案，否則 x 和 y 的和將是答案。

實現

我們已經看到了示例和找到解決方案的思路，現在讓我們來實現程式碼 -

• 首先，我們將建立一個函式，該函式將接收三個整數並返回一個整數。

• 在函式中，首先我們將所有整數儲存在一個向量中，然後對向量進行排序以獲取頻率最低的整數。

• 我們將獲得所有給定元素的總和，併除以 3 以獲得我們可以建立的最大字串數量。

• 稍後，我們將比較最大字串的值與頻率最低的兩個字元的和。如果和較小，我們將最大字串更新為頻率最低的兩個元素的和。

• 最後，我們將返回最大可能字串的值，並在主函式中打印出來。

示例

#include <bits/stdc++.h>
using namespace std;
int count(int a, int b, int c){
   // storing the values in the vector 
   vector<int>temp(3);
   temp[0] = a;
   temp[1] = b;
   temp[2] = c; 
   
   // sorting the vector to get the minimum two elements 
   sort(temp.begin(), temp.end());
   
   // counting the sum of all the elements 
   int maxStrings = (a+b+c)/3;    
   if(temp[0] + temp[1] < maxStrings){
      maxStrings = temp[0] + temp[1];
   }    
   return maxStrings; // returning the final answer
}
int main(){

   // given numbers 
   int a = 3;
   int b = 2;
   int c = 4;
   cout<<"The count of 3 length strings using given characters containing at least 2 different characters is "<<count(a,b,c)<<endl;   
   return 0;
}

輸出

The count of 3 length strings using given characters containing at least 2 different characters is 3

時間和空間複雜度

上面程式碼的時間複雜度為 O(1) 或常數，因為我們沒有使用任何迴圈或遞迴呼叫來獲取結果。

上面程式碼的空間複雜度為 O(1)，因為我們在這裡沒有使用額外的空間。

結論

在本教程中，我們實現了一個程式來查詢使用給定字元構成至少包含兩個不同字元的長度為 3 的字串的個數為 3。我們討論了樸素方法，並實現了具有常數時間和空間複雜度（即 O(1)）的數學方法。