Total Strings

Posted: 13 Jan, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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
Approach 1
  • 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.
Try Problem