C++ 长度为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个不同的字符。

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的字符串的数量，其中至少包含2个不同的字符。我们讨论了朴素方法，并使用了时间和空间复杂度为O(1)的数学方法来实现。