使用给定的字符，计算长度为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中文网其他相关文章！