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

- String is only built with
**'a'**, i.e., n**'a'**forms the string.

Count of such string is: 1 - 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 - 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. - 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'**. - 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. - 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=2Case 1:String is only built with 'a', i.e., n 'a' forms the string "aa" Total under this category: 1Case 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: 0Case 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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.

Learn PCB Designing: PCB DESIGNING TUTORIAL