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

In this article, we are going to find number of strings that can be formed under given constraints. This is a pure combinatorial problem that was featured in Google interview.
Submitted by Radib Kar, on March 02, 2019 [Last updated : March 20, 2023]

## Problem Description

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.

## Example

```    Input:
n=1

Output:
3
Possible strings are:
"a", "b", "c"

Input:
n=2

Output:
8
Possible strings are:
"aa", "ab", "ac", "ba", "ca", "bc", "cb", "cc"
```

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

String alphabets are only {a, b, c}

Length of string is n. (n>0)

Let's consider what can be the possible cases

1. String is only built with 'a', i.e., n 'a' forms the string.
Count of such string is: 1
2. String built with one 'b' & n-1 'a'
Count of such string is: (n/1)=n
One 'b' can be placed at any of n positions, that's why n number of such strings
3. String built with one 'b', one 'c' and (n-2) 'a'
Count of such string (n/2)*2=n*(n-1)
One 'b' and one 'c' can take any of two places out of n and any of 'b' & 'c' can comes first.
4. String built with one 'b', two 'c' and (n-3) 'a'
Count of such string (n/3)*3=n*(n-1)*(n-2)/2
One 'b' and two 'c' can take any of three places out of n and there are 3 combinations possible between one 'b' & two 'c'.
5. String built with two 'c' and (n-2) 'a'
Count of such string (n/2)=n*(n-1)/2
Two 'c' can take any two of n places.
6. String built with one 'c' and (n-1) 'a'
Count of such string (n/1)=n
One 'c' can take any of one places out of n.

### Example with explanation

```    Let n=2
Case 1: String is only built with 'a', i.e., n 'a' forms the string
"aa"
Total under this category: 1

Case 2: String built with one 'b' & n-1 'a'
"ab"
"ba"
Total under this category: 2//(n)

Case 3: String built with one 'b', one 'c' and (n-2) 'a'
"bc"
"cb"
Total under this category: 2//(n*(n-1))

Case 4: String built with one 'b', two 'c' and (n-3) 'a'
No string in this category
Total under this category: 0

Case 5: String built with two 'c' and (n-2) 'a'
"cc"
Total under this category: 1//(n*(n-1)/2)

Case 6: String built with one 'c' and (n-1) 'a'
"ac"
"ca"
Total under this category: 2//(n)

Total no of strings possible: 1+2+2+0+1+2=8
```

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

```#include <bits/stdc++.h>
using namespace std;

int find(int n)
{
//total no of string possible(for details check solution part)
return 1 + (n) + n * (n - 1) + n * (n - 1) * (n - 2) / 2 + n * (n - 1) / 2 + n;
}

int main()
{
int n;

cout << "enter length of string\n";
cin >> n;

cout << "Number of string possible under ";
cout << "constraints is : " << find(n) << endl;

return 0;
}
```

### Output

```First run:
enter length of string
2
Number of string possible under constraints is : 8

Second run:
enter length of string
4
Number of string possible under constraints is : 39
```