Google Interview questions Strings count

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

This problem can be solved by taking each case separately and then we will sum there result

Case1: All letter a, number of ways we can form this is 1

Case2: 1’b’ and reaming letter with ‘a’ that is 1b and (n-1) a, this problem can be solved by thinking we have one ‘b’ and reaming all a like a1, a2 …. an The number of ways we can arrange them is n! but here a1 is exactly same as a2 and so on. So n! is not correct

Let take an example, let assume n=3, then we have letter like b,a1,a2 we can arrange them like below n! that is 6 ways

b,a1,a2
b,a2,a1
a1,a2,b
a2,a1,b
a1,b,a2
a2,b,a1

But here a1 and a2 is same that is b,a1,a2 is same as b,a2,a1 so to find the exact number of ways, we have to remove the duplicate which will be 3!/2!

So 1b and (n-1) can be arrange in n!/(n-1)!= n

Case3: 1 ‘b’, 1 ‘c’ and (n-2) a number of ways will be n!/(n-2)! = n(n-1)

Case4: 1 ‘b’, 2 ‘c’ and (n-3) a number of ways will be n!/2!*(n-3)!= n(n-1)(n-2)/2

Case5: 1 ‘c’ and (n-1) a number of ways will be n!/(n-1)!= n

Case6: 2 ‘c’ and (n-2) a number of ways will be as n!/2!*(n-2)!= n(n-1)/2

So total number of ways will be 1+n+n(n-1)+n(n-1)(n-2)/2+n+n(n-1)/2 which is equal to 1+2n+n(n-1)(n-2)/2+n(n-1)/2

With the above formula we can have the program like below with o(1) time complexity.

public class StringCount {
 public static void main(String[] args) {
 System.out.println(countWays(5));
 }
 
 public static int countWays(int n) {
 return 1+(2*n)+ n*(n-1) + n*(n-1) * (n-2)/2 + n*(n-1)/2;
 }
}