使用给定字符构成至少包含两个不同字符的长度为 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)）的数学方法。