Colorful Strings

Moderate
0/80
Average time to solve is 10m
profile
Contributed by
4 upvotes
Asked in companies
DirectiShareChat

Problem statement

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’.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

2
3 1 1 1
4 1 1 1

Sample Output 1 :

6
36

Explanation Of Sample Output 1 :

For the first test case, “RGB”, “RBG”, “GBR”, “GRB”, “BRG” and “BGR” are 6 possible permutations possible.

For the second test case, the following 3 cases are possible.
“RGBB” and its 12 permutations.
“RGBR” and its 12 permuations.
“RGBB” and its 12 permuations.
 So total permutations = 12 + 12 + 12 = 36

Sample Input 2 :

2
3 0 0 0 
2 1 1 0

Sample Output 2 :

27
2
Hint

Can you think of fixing the number of ‘R’s, ‘G’s and ‘B’s used in the string?

Approaches (1)
Brute Force

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:

  1. Create an array/list “fact” where the i-th index will store i ! (i factorial). Update “fact” as fact[0] = 1.
  2. Create a loop using a variable ‘i’ such that 1 <= i <= ‘N’.
    1. Update “fact” as fact[i] = (fact[i - 1] * i ).
  3. Create and initialize a variable “ans” to zero which stores the count of all possible strings.
  4. 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]).
  5. Return “ans”.
Time Complexity

O(N ^ 2), where ‘N’ is the length of the string.

 

We are pre-computing the “fact” array/list which takes O(N) and then we are using a nested loop where each loop runs for O(N) time.  So the overall time complexity will be O(N) + O(N ^ 2) = O(N^2).

Space Complexity

O(N), where ‘N’ is the length of the string.

 

Since we are using an array/list to store the factorial of each number upto ‘N’. So the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Colorful Strings
Full screen
Console