Last Updated: 13 Jan, 2021
Total Strings
Moderate
Asked in companies
You are given a positive integer 'N'. Your task is to find the number of strings of length ‘N’ that can be formed using only the characters ‘a’, ‘b’ and ‘c’. The strings formed should be such that the number of ‘b’ and ‘c’ in the string is at most 1 and 2, respectively.
Example:
Let’s say N = 2. The strings of length 2, which satisfy the given constraints are: “aa”, “ab”, “ac”, “ba”, “bc”, “ca”, “cb”, “cc”. Hence, the output is 8.
Input Format:
The first line of input contains an integer ‘T’ representing the number of test cases.
The first and the only line of every test case contains a positive integer ‘N’ representing the length of strings to be found.
Output Format:
For each test case, the number of strings of length ‘N’ which satisfy the given constraints is printed.
Print the output of each test case in a separate line.
Note:
Since the number of possible strings can be very large, print the answer modulo 1000000007.
You do not need to print anything, it has already been taken care of. Just implement the given function.
Follow Up:
Can you solve the problem in constant time and using constant extra space i.e. O(1) time and space complexity?
Constraints:
1 <= T <= 100
1 <= N <= 3000
Where 'T' denotes the number of test cases, 'N' denotes the length of strings.
Time Limit: 1 sec
Approaches
- A brute force approach could be to generate all the strings of length ‘N’ which satisfy the given constraints.
- The idea is to use recursion for generating a string. On every recursive call, we add one of the characters from ‘a’, ‘b’ and ‘c’ to the string.
- When the complete string of length ‘N’ is generated, we increment the counter by one.
- While generating a string, we keep track of the frequency of characters ‘b’ and ‘c’ present in the string. If it exceeds the given constraints, we discard that string.
- As the counter gets incremented every time a valid string is generated. Hence, it holds the final answer.
- In this way, we have solved a larger problem by dividing it into smaller sub-problems.
Algorithm:
- Let ‘M’ denote the remaining number of characters which we need, to generate a string of length ‘N’.
- Recursive function: countStringsHelper(M, FrequencyB, FrequencyC).
- Initially, we start with an empty string, so we call the function with M = N.
- Base Condition 1: If the frequency of ‘b’ and ‘c’ in the string generated so far, do not satisfy the given constraints, then Return 0.
- Base Condition 2: If M=0, then we have generated a valid string. So, Return 1.
- Base Condition 3: If Frequency[‘b’] = 1 and Frequency[‘c’] = 2, then the remaining characters in the string must be ‘a’. Hence, only one string is possible. So, Return 1.
- Assuming ‘a’ as the next character:
- Append it to the current string.
- Recursively call the function to generate the remaining string (M-1 characters).
- Add the returned value from each recursive call to the counter.
- Repeat the previous step for ‘b’ and ‘c’.
- Return the counter.
- This approach is similar to the previous one. But in the previous approach, the same subproblem is being solved multiple times i.e the recursive function is being called with the same parameters multiple times.
- This can be seen in the recursion tree of the problem, shown below:
- The idea is to use the concept of memoization.
- We store the results of the subproblems which we have already solved in a 3D array and return it whenever required.
- This way we can avoid solving the same subproblems again and again.
Algorithm:
- Create a 3D array Memo of size (N+1)*2*3 and initialize it with -1.
- Memo[i][j][k] represents the count of strings of length ‘N-i’, which contains ‘j’ number of ‘b’ and ‘k’ number of ‘c’.
- Let ‘M’ denote the remaining number of characters which we need, to generate a string of length ‘N’.
- Recursive function: countStringsHelper(M, FrequencyB, FrequencyC).
- Initially, we start with an empty string, so we call the function with M = N.
- Base Condition 1: If the frequency of ‘b’ and ‘c’ in the string generated so far do not satisfy the given constraints, then Return 0.
- Base Condition 2: If M=0, then we have generated a valid string. So, Return 1.
- Base Condition 3: If Frequency[‘b’] = 1 and Frequency[‘c’] = 2, then the remaining characters in the string must be ‘a’. Hence, only one string is possible. So, Return 1.
- Now, If Memo[M][FrequencyB][FrequencyC] != -1, it means this subproblem has been solved before. So, just return its result.
- Otherwise, Assuming ‘a’ as the next character:
- Append it to the current string.
- Recursively call the function to generate the remaining string (M-1 characters).
- Add the returned value from each recursive call to the counter.
- Repeat the previous step for ‘b’ and ‘c’.
- Set Memo[M][FrequencyB][FrequencyC] = counter, and return counter.
- Memo[N][0][0] stores the final answer.
- The problem has small constraints for the frequency of characters ‘b’ and ‘c’. Hence, we can easily derive the formula for any given ‘N’. And use this formula to calculate the number of possible strings.
- In order to derive the formula, we consider all the possible cases:
- Case 1: All the characters in the string are ‘a’. This will give us only 1 possible string.
- Case 2: One character ‘b’ and remaining ‘a’. Using permutations and combinations we can say the number of possible strings will be (N! / (N-1)!) i.e. N.
- Case 3: One character ‘b’, One character ‘c’ and remaining ‘a’. Using permutations and combinations we can say the number of possible strings will be (N! / (N-2)!) i.e. N*(N-1).
- Case 4: One character ‘b’, Two characters ‘c’ and remaining ‘a’. Number of possible strings will be (N! / (2! * (N-3)!)) i.e. N*(N-1)*(N-2)/2.
- Case 5: One character ‘c’ and remaining ‘a’. Similar to case 2. So, we can say the number of possible strings will be N.
- Case 6: Two characters ‘c’ and remaining ‘a’. Number of possible strings will be (N! / (2! * (N-2)!)) i.e. N*(N-1)/2.
- Adding all the above cases we get the formula: 1 + 2*N + N*(N*N - 1)/2.
Similar problems