Using the given characters, count the number of strings of length 3 that contain at least 2 different characters

Give us three integers "a", "b" and "c", representing the frequency of occurrence of three different characters "A", "B" and "C". We have to find the number of different strings that can be formed using these characters, and at least two different characters must be present in the formed string. We will see two ways to solve this problem, one is naive and the other is mathematical.

Example

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

Output:  3 

illustrate

We can create three strings "ABC", "ABC" and "ACC". We use 'A' 3 times, 'B' 2 times, and 'C' 4 times in these strings, which is the same or less frequency than they are given, and all strings contain at least 2 different characters .

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

Output: 4

illustrate

We can create the strings "ACC", "BCC", "BCC" and "BCC". We have used all the given characters except the two "C"s, since there are no other characters to create a new string with. If we had tried other combinations, the final number of strings would have been less.

Naive method

The simplest way is to find all possible combinations of given frequencies, but the problem is that this takes a lot of time complexity and is extremely inefficient.

We have to generate all possible substrings, and if our numbers are large, it will take a lot of time and space that a computer can't handle.

mathematical method

idea

The idea behind this approach is that we need at least two distinct characters in the string, so we will always try to focus on the least frequent character.

The maximum number of strings we can make is (a b c)/3, and the possible number only depends on the frequency of occurrence of at least two.

Suppose, if at least two frequencies are x and y, then their sum is greater than or equal to (a b c)/3 then we can print this value as the answer, otherwise the sum of x and y is the answer.

Implementation

We have seen examples and ideas for finding solutions, now let’s start implementing the code -

• First, we will create a function that accepts three integers and returns an integer.

• In the function, we first store all the integers in a vector and then sort the vector to get the minimum frequency integer.

• We will get the sum of all the given elements and then divide by 3 to get the maximum number of strings we can make.

• Later, we will compare the value of the largest string with the value of the smallest sum of two frequencies. If the sum is smaller, then we update the maximum string to be the sum of at least two frequency elements.

• Finally, we will return the value of the largest possible string and print it in the main function.

Example

#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;
}

Output

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

Time and space complexity

The time complexity of the above code is O(1) or constant because we are not using any loops or recursive calls to get the results.

The space complexity of the above code is O(1) because we are not using extra space here.

in conclusion

In this tutorial, we implemented a program that finds 3 length strings with count 3 using a given character that contains at least 2 different characters. We discussed simple methods and implemented mathematical methods with constant time and space complexity i.e. O(1).

The above is the detailed content of Using the given characters, count the number of strings of length 3 that contain at least 2 different characters. For more information, please follow other related articles on the PHP Chinese website!