使用給定的字符，計算長度為3的字串的數量，其中至少包含2個不同的字符

給我們三個整數“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 次，這與它們給定的頻率相同或更少，並且所有字串都包含至少2 個不同的字符。 p>

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)，因為我們在這裡沒有使用額外的空間。

結論

在本教程中，我們實作了一個程序，使用包含至少 2 個不同字元的給定字元來尋找 3 個長度字串的計數為 3。我們討論了簡單方法，並實現了具有恆定時間和空間複雜度的數學方法即 O(1)。

以上是使用給定的字符，計算長度為3的字串的數量，其中至少包含2個不同的字符的詳細內容。更多資訊請關注PHP中文網其他相關文章！