## Facebook Interview Question

Software Development Managers**Country:**United States

A straightforward DP problem

```
N = 10
dp = [[[1] * (N+1) for _ in [0,1]] for _ in [0,1,2]]
for l in range(1,N+1):
dp[2][1][l] = dp[2][1][l-1] + dp[2][0][l-1] + dp[1][1][l-1]
dp[1][1][l] = dp[1][1][l-1] + dp[1][0][l-1] + dp[0][1][l-1]
dp[0][1][l] = dp[0][1][l-1] + dp[0][0][l-1]
dp[2][0][l] = dp[2][0][l-1] + dp[1][0][l-1]
dp[1][0][l] = dp[1][0][l-1] + dp[0][0][l-1]
print (dp[2][1][N])
```

I think this can just be calculated (O(1)) (in code need to handle correctly cases of n < 3)

1+n+n+(n choose 2) + n*(n-1) + n*(n -1 choose 2)

1 - case of all As

n - case of all As and B

n - case of all As and C

(n choose 2) - case of all As and 2Cs

n*(n-1) - case of All As and B and C

n*(n -1 choose 2)- case of All As and B and 2 Cs

The problem is to output the total count of the strings that fit the criteria (length = n, bCount <= 1, cCount <=2)

Algorithm:

- Find all the possible combinations of aCount, bCount, cCount to form the string of length n;

Ex: n = 3 : aCount = 3, bCount = 0, cCount = 0; meaning there are 3 'a's, 0 'b' and 0 'c'in that string

aCount = 2, bCount = 1, cCount = 0;

aCount = 1, bCount = 1, cCount = 1;

.....

- Eliminate combinations that don't meet the criteria which is bCount <= 1 and cCount <= 2;

- For each combinations, calculate the number of distinct permutations

Ex: n = 4 : aCount = 2, bCount = 0, cCount = 2 ----> totalPermutations = n! / (aCount!*bCount!*cCount!) (This is a formulas for finding number of distict permutations)

In this case it would be 4!/(2!*0!*2!) = 6

- Add them all up to get the answer

Code:

```
public static int n = 4;
static void Main(string[] args)
{
string str = "";
int aCount = 0;
int bCount = 0;
int cCount = 0;
int answer = 0;
for (int a = 0; a <= n; a++)
{
aCount = a;
for (int b = 0; b <= n - aCount; b++)
{
bCount = b;
if (bCount > 1)
continue;
cCount = n - (aCount + bCount);
if (cCount > 2)
continue;
Console.WriteLine(aCount +" "+bCount+" "+cCount);
answer = answer + (Factorial(n) / (Factorial(aCount) * Factorial(bCount) * Factorial(cCount)));
}
}
Console.WriteLine(answer);
}
static int Factorial(int n)
{
int result = 1;
for (int i = 1; i <=n; i++)
{
result = result * i;
}
return result;
}
```

Output:

n = 1. Output: 3;

n = 2. Output: 8;

n = 3. Output: 19;

n = 4. Output: 39;

.

.

.

How about recursion, where the initial call is GetNumCombinations(n, empty string, allowedLetters) where allowedLetters is a hashmap in which the keys represent the allowed input letters, e.g. {a,b,c}, and their respective values the number of times they're allowed to be used, where -1 is unlimited, e.g. {-1,1,2}.

(Excuse my blend of code and pseudo-code)

int GetNumCombinations(int n, string s, hashmap[char,int] allowedLetters)

int totalCombinations = 0;

if size of s == n then

return 1;

else

for each allowedLetter in allowedLetters keys:

create copy of allowedLettershashmap: tempAllowedLetters

lookup allowedLetter in tempAllowedLetters:

if value == 1 then

remove mapping from tempAllowedLetters

else

subtract 1 from value in mapping

totalCombinations += GetTotalCombinations(n, s append allowedLetter, tempAllowedLetters);

return totalCombinations

How about recursion, where the initial call is GetNumCombinations(n, empty string, allowedLetters) where allowedLetters is a hashmap in which the keys represent the allowed input letters, e.g. [a,b,c], and their respective values the number of times they're allowed to be used, where -1 is unlimited, e.g. [-1,1,2].

int GetNumCombinations(int n, string s, hashmap[char,int] allowedLetters)

int totalCombinations = 0;

if size of s == n then

totalCombinations = 1;

else

for each allowedLetter in allowedLetters keys:

create copy of allowedLetters: tempAllowedLetters

lookup allowedLetter in tempAllowedLetters:

if value == 1 then

remove mapping from tempAllowedLetters

else

subtract 1 from value in mapping

totalCombinations += GetTotalCombinations(n, s append allowedLetter, tempAllowedLetters);

return totalCombinations;

How about recursion, where the initial call is GetNumCombinations(n, empty string, allowedLetters) where allowedLetters is a hashmap in which the keys represent the allowed input letters, e.g. {a,b,c}, and their respective values the number of times they're allowed to be used, where -1 is unlimited, e.g. {-1,1,2}.

int GetNumCombinations(int n, string s, hashmap[char,int] allowedLetters)

int totalCombinations = 0;

if size of s == n then

totalCombinations = 1;

else

for each allowedLetter in allowedLetters keys:

create copy of allowedLetters: tempAllowedLetters

lookup allowedLetter in tempAllowedLetters:

if value == 1 then

remove mapping from tempAllowedLetters

else

subtract 1 from value in mapping

totalCombinations += GetTotalCombinations(n, s append allowedLetter, tempAllowedLetters);

return totalCombinations;

geeksforgeeks count-strings-can-formed-using-b-c-given-constraints

- anoophky September 07, 2019