# Count of strings that can be formed using a, b and c under given constraints

Given a length n, count the number of strings of length n that can be made using ‘a’, ‘b’ and ‘c’ with at-most one ‘b’ and two ‘c’s allowed.

Examples :

```Input : n = 3
Output : 19
aaa aab aac aba abc aca acb acc baa
bac bca bcc caa cab cac cba cbc cca ccb

Input  : n = 4
Output : 39
```

A simple solution is to recursively count all possible combination of string that can be mode up to latter ‘a’, ‘b’, and ‘c’.

Below is implementation of above idea

## C++

 `// C++ program to count number of strings ` `// of n characters with ` `#include ` `using` `namespace` `std; ` ` `  `// n is total number of characters. ` `// bCount and cCount are counts of 'b' ` `// and 'c' respectively. ` `int` `countStr(``int` `n, ``int` `bCount, ``int` `cCount) ` `{ ` `    ``// Base cases ` `    ``if` `(bCount < 0 || cCount < 0) ``return` `0; ` `    ``if` `(n == 0) ``return` `1; ` `    ``if` `(bCount == 0 && cCount == 0) ``return` `1; ` ` `  `    ``// Three cases, we choose, a or b or c ` `    ``// In all three cases n decreases by 1. ` `    ``int` `res = countStr(n-1, bCount, cCount); ` `    ``res += countStr(n-1, bCount-1, cCount); ` `    ``res += countStr(n-1, bCount, cCount-1); ` ` `  `    ``return` `res; ` `} ` ` `  `// Driver code ` `int` `main() ` `{ ` `    ``int` `n = 3;  ``// Total number of characters ` `    ``cout << countStr(n, 1, 2); ` `    ``return` `0; ` `} `

## Java

 `// Java program to count number  ` `// of strings of n characters with ` `import` `java.io.*; ` ` `  `class` `GFG  ` `{ ` `     `  `// n is total number of characters. ` `// bCount and cCount are counts of 'b' ` `// and 'c' respectively. ` `static` `int` `countStr(``int` `n,  ` `                    ``int` `bCount,  ` `                    ``int` `cCount) ` `{ ` `    ``// Base cases ` `    ``if` `(bCount < ``0` `|| cCount < ``0``) ``return` `0``; ` `    ``if` `(n == ``0``) ``return` `1``; ` `    ``if` `(bCount == ``0` `&& cCount == ``0``) ``return` `1``; ` ` `  `    ``// Three cases, we choose, a or b or c ` `    ``// In all three cases n decreases by 1. ` `    ``int` `res = countStr(n - ``1``, bCount, cCount); ` `    ``res += countStr(n - ``1``, bCount - ``1``, cCount); ` `    ``res += countStr(n - ``1``, bCount, cCount - ``1``); ` ` `  `    ``return` `res; ` `} ` ` `  `// Driver code ` `public` `static` `void` `main (String[] args) ` `{ ` `    ``int` `n = ``3``; ``// Total number of characters ` `    ``System.out.println(countStr(n, ``1``, ``2``)); ` `} ` `} ` ` `  `// This code is contributed by akt_mit `

## Python 3

 `# Python 3 program to  ` `# count number of strings ` `# of n characters with ` ` `  `# n is total number of characters. ` `# bCount and cCount are counts  ` `# of 'b' and 'c' respectively. ` `def` `countStr(n, bCount, cCount): ` ` `  `    ``# Base cases ` `    ``if` `(bCount < ``0` `or` `cCount < ``0``): ` `        ``return` `0` `    ``if` `(n ``=``=` `0``) : ` `        ``return` `1` `    ``if` `(bCount ``=``=` `0` `and` `cCount ``=``=` `0``): ` `        ``return` `1` ` `  `    ``# Three cases, we choose, a or b or c ` `    ``# In all three cases n decreases by 1. ` `    ``res ``=` `countStr(n ``-` `1``, bCount, cCount) ` `    ``res ``+``=` `countStr(n ``-` `1``, bCount ``-` `1``, cCount) ` `    ``res ``+``=` `countStr(n ``-` `1``, bCount, cCount ``-` `1``) ` ` `  `    ``return` `res ` ` `  `# Driver code ` `if` `__name__ ``=``=``"__main__"``: ` `    ``n ``=` `3` `# Total number of characters ` `    ``print``(countStr(n, ``1``, ``2``)) ` ` `  `# This code is contributed  ` `# by ChitraNayal `

## C#

 `// C# program to count number  ` `// of strings of n characters  ` `// with a, b and c under given ` `// constraints ` `using` `System; ` ` `  `class` `GFG ` `{ ` `     `  `// n is total number of  ` `// characters. bCount and ` `// cCount are counts of  ` `// 'b' and 'c' respectively. ` `static` `int` `countStr(``int` `n,  ` `                    ``int` `bCount,  ` `                    ``int` `cCount) ` `{ ` `    ``// Base cases ` `    ``if` `(bCount < 0 || cCount < 0)  ` `        ``return` `0; ` `    ``if` `(n == 0) ``return` `1; ` `    ``if` `(bCount == 0 && cCount == 0)  ` `        ``return` `1; ` ` `  `    ``// Three cases, we choose,  ` `    ``// a or b or c. In all three ` `    ``// cases n decreases by 1. ` `    ``int` `res = countStr(n - 1,  ` `                       ``bCount, cCount); ` `    ``res += countStr(n - 1,  ` `                    ``bCount - 1, cCount); ` `    ``res += countStr(n - 1,  ` `                    ``bCount, cCount - 1); ` ` `  `    ``return` `res; ` `} ` ` `  `// Driver code ` `static` `public` `void` `Main () ` `{ ` `    ``// Total number  ` `    ``// of characters ` `    ``int` `n = 3;  ` `    ``Console.WriteLine(countStr(n, 1, 2)); ` `} ` `} ` ` `  `// This code is contributed by aj_36 `

## PHP

 ` `

Output :

`19`

Time complexity of above solution is exponential.

Efficient Solution
If we drown a recursion tree of above code, we can notice that same values appear multiple times. So we store results which are used later if repeated.

## C++

 `// C++ program to count number of strings ` `// of n characters with ` `#include ` `using` `namespace` `std; ` ` `  `// n is total number of characters. ` `// bCount and cCount are counts of 'b' ` `// and 'c' respectively. ` `int` `countStrUtil(``int` `dp[], ``int` `n, ``int` `bCount=1, ` `                 ``int` `cCount=2) ` `{ ` `    ``// Base cases ` `    ``if` `(bCount < 0 || cCount < 0) ``return` `0; ` `    ``if` `(n == 0) ``return` `1; ` `    ``if` `(bCount == 0 && cCount == 0) ``return` `1; ` ` `  `    ``// if we had saw this combination previously ` `    ``if` `(dp[n][bCount][cCount] != -1) ` `        ``return` `dp[n][bCount][cCount]; ` ` `  `    ``// Three cases, we choose, a or b or c ` `    ``// In all three cases n decreases by 1. ` `    ``int` `res = countStrUtil(dp, n-1, bCount, cCount); ` `    ``res += countStrUtil(dp, n-1, bCount-1, cCount); ` `    ``res += countStrUtil(dp, n-1, bCount, cCount-1); ` ` `  `    ``return` `(dp[n][bCount][cCount] = res); ` `} ` ` `  `// A wrapper over countStrUtil() ` `int` `countStr(``int` `n) ` `{ ` `    ``int` `dp[n+1]; ` `    ``memset``(dp, -1, ``sizeof``(dp)); ` `    ``return` `countStrUtil(dp, n); ` `} ` ` `  `// Driver code ` `int` `main() ` `{ ` `    ``int` `n = 3; ``// Total number of characters ` `    ``cout << countStr(n); ` `    ``return` `0; ` `} `

## Java

 `// Java program to count number of strings  ` `// of n characters with  ` ` `  `class` `GFG  ` `{ ` `    ``// n is total number of characters.  ` `    ``// bCount and cCount are counts of 'b'  ` `    ``// and 'c' respectively.  ` ` `  `    ``static` `int` `countStrUtil(``int``[][][] dp, ``int` `n, ` `                            ``int` `bCount, ``int` `cCount)  ` `    ``{ ` ` `  `        ``// Base cases  ` `        ``if` `(bCount < ``0` `|| cCount < ``0``)  ` `        ``{ ` `            ``return` `0``; ` `        ``} ` `        ``if` `(n == ``0``) ` `        ``{ ` `            ``return` `1``; ` `        ``} ` `        ``if` `(bCount == ``0` `&& cCount == ``0``)  ` `        ``{ ` `            ``return` `1``; ` `        ``} ` ` `  `        ``// if we had saw this combination previously  ` `        ``if` `(dp[n][bCount][cCount] != -``1``)  ` `        ``{ ` `            ``return` `dp[n][bCount][cCount]; ` `        ``} ` ` `  `        ``// Three cases, we choose, a or b or c  ` `        ``// In all three cases n decreases by 1.  ` `        ``int` `res = countStrUtil(dp, n - ``1``, bCount, cCount); ` `        ``res += countStrUtil(dp, n - ``1``, bCount - ``1``, cCount); ` `        ``res += countStrUtil(dp, n - ``1``, bCount, cCount - ``1``); ` ` `  `        ``return` `(dp[n][bCount][cCount] = res); ` `    ``} ` ` `  `    ``// A wrapper over countStrUtil()  ` `    ``static` `int` `countStr(``int` `n, ``int` `bCount, ``int` `cCount)  ` `    ``{ ` `        ``int``[][][] dp = ``new` `int``[n + ``1``][``2``][``3``]; ` `        ``for` `(``int` `i = ``0``; i < n + ``1``; i++)  ` `        ``{ ` `            ``for` `(``int` `j = ``0``; j < ``2``; j++)  ` `            ``{ ` `                ``for` `(``int` `k = ``0``; k < ``3``; k++)  ` `                ``{ ` `                    ``dp[i][j][k] = -``1``; ` `                ``} ` `            ``} ` `        ``} ` `        ``return` `countStrUtil(dp, n,bCount,cCount); ` `    ``} ` ` `  `    ``// Driver code  ` `    ``public` `static` `void` `main(String[] args)  ` `    ``{ ` `        ``int` `n = ``3``; ``// Total number of characters  ` `        ``int` `bCount = ``1``, cCount = ``2``; ` `        ``System.out.println(countStr(n,bCount,cCount)); ` `    ``} ` `} ` ` `  `// This code has been contributed by 29AjayKumar `

## C#

 `// C# program to count number of strings  ` `// of n characters with  ` `using` `System;  ` ` `  `class` `GFG  ` `{  ` `    ``// n is total number of characters.  ` `    ``// bCount and cCount are counts of 'b'  ` `    ``// and 'c' respectively.  ` `    ``static` `int` `countStrUtil(``int``[,,] dp, ``int` `n,  ` `                    ``int` `bCount=1, ``int` `cCount=2)  ` `    ``{  ` `        ``// Base cases  ` `        ``if` `(bCount < 0 || cCount < 0) ` `            ``return` `0;  ` `        ``if` `(n == 0)  ` `            ``return` `1;  ` `        ``if` `(bCount == 0 && cCount == 0)  ` `            ``return` `1;  ` `     `  `        ``// if we had saw this combination previously  ` `        ``if` `(dp[n,bCount,cCount] != -1)  ` `            ``return` `dp[n,bCount,cCount];  ` `     `  `        ``// Three cases, we choose, a or b or c  ` `        ``// In all three cases n decreases by 1.  ` `        ``int` `res = countStrUtil(dp, n - 1, bCount, cCount);  ` `        ``res += countStrUtil(dp, n - 1, bCount - 1, cCount);  ` `        ``res += countStrUtil(dp, n - 1, bCount, cCount - 1);  ` `     `  `        ``return` `(dp[n, bCount, cCount] = res);  ` `    ``}  ` `     `  `    ``// A wrapper over countStrUtil()  ` `    ``static` `int` `countStr(``int` `n)  ` `    ``{  ` `        ``int``[,,] dp = ``new` `int``[n + 1, 2, 3];  ` `        ``for``(``int` `i = 0; i < n + 1; i++) ` `            ``for``(``int` `j = 0; j < 2; j++) ` `                ``for``(``int` `k = 0; k < 3; k++) ` `                    ``dp[i, j, k] = -1; ` `        ``return` `countStrUtil(dp, n);  ` `    ``}  ` `     `  `    ``// Driver code  ` `    ``static` `void` `Main()  ` `    ``{  ` `        ``int` `n = 3; ``// Total number of characters  ` `         `  `        ``Console.Write(countStr(n));  ` `    ``} ` `} ` ` `  `// This code is contributed by DrRoot_ `

Output :

```19
```

Time Complexity : O(n)
Auxiliary Space : O(n)

Thanks to Mr. Lazy for suggesting above solutions.

A solution that works in O(1) time :

## C++

 `// A O(1) CPP program to find number of strings ` `// that can be made under given constraints. ` `#include ` `using` `namespace` `std; ` `int` `countStr(``int` `n) ` `{ ` `    ``return` `1+(n*2)+(n*((n*n)-1)/2); ` `} ` ` `  `// Driver code  ` `int` `main() ` `{ ` `  ``int` `n = 3; ` `  ``cout << countStr(n); ` `  ``return` `0; ` `}  `

## Java

 `// A O(1) Java program to  ` `// find number of strings ` `// that can be made under ` `// given constraints. ` `import` `java.io.*; ` ` `  `class` `GFG ` `{ ` `    ``static` `int` `countStr(``int` `n) ` `    ``{ ` `    ``return` `1` `+ (n * ``2``) +  ` `           ``(n * ((n * n) - ``1``) / ``2``); ` `    ``} ` ` `  `// Driver code  ` `public` `static` `void` `main (String[] args) ` `{ ` `    ``int` `n = ``3``; ` `    ``System.out.println( countStr(n)); ` `} ` `} ` ` `  `// This code is contributed by ajit `

## Python 3

 `# A O(1) Python3 program to find  ` `# number of strings that can be ` `# made under given constraints. ` ` `  `def` `countStr(n): ` `    ``return` `(``1` `+` `(n ``*` `2``) ``+`  `                ``(n ``*` `((n ``*` `n) ``-` `1``) ``/``/` `2``)) ` ` `  `# Driver code  ` `if` `__name__ ``=``=` `"__main__"``: ` `    ``n ``=` `3` `    ``print``(countStr(n)) ` ` `  `# This code is contributed ` `# by ChitraNayal `

## C#

 `// A O(1) C# program to  ` `// find number of strings ` `// that can be made under ` `// given constraints. ` `using` `System; ` ` `  `class` `GFG ` `{ ` `    ``static` `int` `countStr(``int` `n) ` `    ``{ ` `    ``return` `1 + (n * 2) +  ` `          ``(n * ((n * n) - 1) / 2); ` `    ``} ` ` `  `// Driver code  ` `static` `public` `void` `Main () ` `{ ` `    ``int` `n = 3; ` `    ``Console.WriteLine(countStr(n)); ` `} ` `} ` ` `  `// This code is contributed by m_kit `

## PHP

 ` `

Output :

`19`

Time Complexity : O(1)
Auxiliary Space : O(1)

Thanks to Niharika Sahai for providing above solution.