Home » Interview coding problems/challenges

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

Problem statement:

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:

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

#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





Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.
Learn PCB Designing: PCB DESIGNING TUTORIAL







Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing » Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates

© https://www.includehelp.com some rights reserved.