Last Updated: 29 Apr, 2021
Colorful Strings
Moderate
Asked in companies
You have been given an integer ‘N’. You are supposed to find the number of all possible strings of length ‘N’ where each character of the string is either ‘R’, ‘B’ or ‘G’. In the final string, there must be at least ‘r’ characters of ‘R, at least ‘b’ characters of ‘B’ and at least ‘g’ characters of ‘G’.
Input Format :
The first line contains an integer ‘T’ denoting the number of test cases. Then each test case follows.
The first input line of each test case contains 4 space-separated integers ‘N’, ‘r’, ‘b’ and ‘g’ described as above in the problem.
Output Format :
For each test case, print the number of all possible strings of length ‘N’ with constraints as described in the problem statement.
The output of each test case will be printed in a separate line.
Note:
You do not need to print anything; it has already been taken care of. Just implement the function.
Constraints :
1 <= T <= 50
1 <= N <= 20
1 <= r <= N
1 <= b <= N
1 <= g <= N
r + g + b <= N
Time limit: 1 sec
Approaches
The key idea of this approach is to fix the number of ‘R’s , ‘G’s and ‘B’s in the string and count all the permutations.
Consider the following steps:
- Create an array/list “fact” where the i-th index will store i ! (i factorial). Update “fact” as fact[0] = 1.
- Create a loop using a variable ‘i’ such that 1 <= i <= ‘N’.
- Update “fact” as fact[i] = (fact[i - 1] * i ).
- Create and initialize a variable “ans” to zero which stores the count of all possible strings.
- Create a loop using the variable ‘i’ which denotes the count of ‘R’s in the string such that r <= ‘i’ <= ‘N’.
- Create a nested loop using a variable ‘j’ which denotes the count of G’s in the string such that g <= ‘j’ <= ‘N’.
- Store the count of ‘B’ in a variable called ‘k’ i.e. ‘k’ = ‘N’ - i - j.
- If ‘k’ is greater than or equal to ‘b’ then we will add the number of permutations possible i.e. ans = ans + (fact[n] / (fact[i] * fact[ j] * fact[k]).
- Create a nested loop using a variable ‘j’ which denotes the count of G’s in the string such that g <= ‘j’ <= ‘N’.
- Return “ans”.