Total Strings

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

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
2
3
Sample Output 1:
8
19
Explanation 1:
For the first test case, refer to the example explained before.

For the second test case, N = 3. The strings of length 3, which satisfy the given constraints are: “aaa”, “aab”, “aac”, “aba”, “abc”, “aca”, “acb”, “acc”, and so on. There are a total of 19 possible strings.
Sample Input 2:
2
4
1
Sample Output 2:
39
3
Hint

Can you solve it using recursion?

Approaches (3)
Using Recursion
  • 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.
Time Complexity

O(3^N), where N is the given positive integer.

 

In the worst case, we are making three recursive calls to the function and the depth of the recursion tree is N. Hence the overall time complexity is O(3^N).

Space Complexity

O(N), where N is the given positive integer.

 

In the worst case, O(N) extra space is required for the recursion stack. Hence, the overall space complexity is O(N).

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