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.
Examples :
Input : n = 3 Output : 19 Below strings follow given constraints: aaa aab aac aba abc aca acb acc baa bac bca bcc caa cab cac cba cbc cca ccb Input : n = 4 Output : 39
Asked in Google Interview
A simple solution is to recursively count all possible combinations of strings that can be made up to latter ‘a’, ‘b’, and ‘c’.
Below is the implementation of the above idea
C++
// C++ program to count number of strings // of n characters with #include<bits/stdc++.h> using namespace std; // n is total number of characters. // bCount and cCount are counts of 'b' // and 'c' respectively. int countStr( int n, int bCount, int cCount) { // Base cases if (bCount < 0 || cCount < 0) return 0; if (n == 0) return 1; if (bCount == 0 && cCount == 0) return 1; // Three cases, we choose, a or b or c // In all three cases n decreases by 1. int res = countStr(n-1, bCount, cCount); res += countStr(n-1, bCount-1, cCount); res += countStr(n-1, bCount, cCount-1); return res; } // Driver code int main() { int n = 3; // Total number of characters cout << countStr(n, 1, 2); return 0; } |
Java
// Java program to count number // of strings of n characters with import java.io.*; class GFG { // n is total number of characters. // bCount and cCount are counts of 'b' // and 'c' respectively. static int countStr( int n, int bCount, int cCount) { // Base cases if (bCount < 0 || cCount < 0 ) return 0 ; if (n == 0 ) return 1 ; if (bCount == 0 && cCount == 0 ) return 1 ; // Three cases, we choose, a or b or c // In all three cases n decreases by 1. int res = countStr(n - 1 , bCount, cCount); res += countStr(n - 1 , bCount - 1 , cCount); res += countStr(n - 1 , bCount, cCount - 1 ); return res; } // Driver code public static void main (String[] args) { int n = 3 ; // Total number of characters System.out.println(countStr(n, 1 , 2 )); } } // This code is contributed by akt_mit |
Python 3
# Python 3 program to # count number of strings # of n characters with # n is total number of characters. # bCount and cCount are counts # of 'b' and 'c' respectively. def countStr(n, bCount, cCount): # Base cases if (bCount < 0 or cCount < 0 ): return 0 if (n = = 0 ) : return 1 if (bCount = = 0 and cCount = = 0 ): return 1 # Three cases, we choose, a or b or c # In all three cases n decreases by 1. res = countStr(n - 1 , bCount, cCount) res + = countStr(n - 1 , bCount - 1 , cCount) res + = countStr(n - 1 , bCount, cCount - 1 ) return res # Driver code if __name__ = = "__main__" : n = 3 # Total number of characters print (countStr(n, 1 , 2 )) # This code is contributed # by ChitraNayal |
C#
// C# program to count number // of strings of n characters // with a, b and c under given // constraints using System; class GFG { // n is total number of // characters. bCount and // cCount are counts of // 'b' and 'c' respectively. static int countStr( int n, int bCount, int cCount) { // Base cases if (bCount < 0 || cCount < 0) return 0; if (n == 0) return 1; if (bCount == 0 && cCount == 0) return 1; // Three cases, we choose, // a or b or c. In all three // cases n decreases by 1. int res = countStr(n - 1, bCount, cCount); res += countStr(n - 1, bCount - 1, cCount); res += countStr(n - 1, bCount, cCount - 1); return res; } // Driver code static public void Main () { // Total number // of characters int n = 3; Console.WriteLine(countStr(n, 1, 2)); } } // This code is contributed by aj_36 |
PHP
<?php // PHP program to count number of // strings of n characters with // n is total number of characters. // bCount and cCount are counts // of 'b' and 'c' respectively. function countStr( $n , $bCount , $cCount ) { // Base cases if ( $bCount < 0 || $cCount < 0) return 0; if ( $n == 0) return 1; if ( $bCount == 0 && $cCount == 0) return 1; // Three cases, we choose, // a or b or c. In all three // cases n decreases by 1. $res = countStr( $n - 1, $bCount , $cCount ); $res += countStr( $n - 1, $bCount - 1, $cCount ); $res += countStr( $n - 1, $bCount , $cCount - 1); return $res ; } // Driver code $n = 3; // Total number // of characters echo countStr( $n , 1, 2); // This code is contributed by ajit ?> |
Javascript
<script> // JavaScript program for the above approach // n is total number of characters. // bCount and cCount are counts of 'b' // and 'c' respectively. function countStr(n, bCount, cCount) { // Base cases if (bCount < 0 || cCount < 0) return 0; if (n == 0) return 1; if (bCount == 0 && cCount == 0) return 1; // Three cases, we choose, a or b or c // In all three cases n decreases by 1. let res = countStr(n - 1, bCount, cCount); res += countStr(n - 1, bCount - 1, cCount); res += countStr(n - 1, bCount, cCount - 1); return res; } // Driver Code let n = 3; // Total number of characters document.write(countStr(n, 1, 2)); // This code is contributed by splevel62. </script> |
19
Time Complexity: O(3^N).
Auxiliary Space: O(1).
Efficient Solution:
If we drown a recursion tree of the above code, we can notice that the same values appear multiple times. So we store results that are used later if repeated.
C++
// C++ program to count number of strings // of n characters with #include<bits/stdc++.h> using namespace std; // n is total number of characters. // bCount and cCount are counts of 'b' // and 'c' respectively. int countStrUtil( int dp[][2][3], int n, int bCount=1, int cCount=2) { // Base cases if (bCount < 0 || cCount < 0) return 0; if (n == 0) return 1; if (bCount == 0 && cCount == 0) return 1; // if we had saw this combination previously if (dp[n][bCount][cCount] != -1) return dp[n][bCount][cCount]; // Three cases, we choose, a or b or c // In all three cases n decreases by 1. int res = countStrUtil(dp, n-1, bCount, cCount); res += countStrUtil(dp, n-1, bCount-1, cCount); res += countStrUtil(dp, n-1, bCount, cCount-1); return (dp[n][bCount][cCount] = res); } // A wrapper over countStrUtil() int countStr( int n) { int dp[n+1][2][3]; memset (dp, -1, sizeof (dp)); return countStrUtil(dp, n); } // Driver code int main() { int n = 3; // Total number of characters cout << countStr(n); return 0; } |
Java
// Java program to count number of strings // of n characters with class GFG { // n is total number of characters. // bCount and cCount are counts of 'b' // and 'c' respectively. static int countStrUtil( int [][][] dp, int n, int bCount, int cCount) { // Base cases if (bCount < 0 || cCount < 0 ) { return 0 ; } if (n == 0 ) { return 1 ; } if (bCount == 0 && cCount == 0 ) { return 1 ; } // if we had saw this combination previously if (dp[n][bCount][cCount] != - 1 ) { return dp[n][bCount][cCount]; } // Three cases, we choose, a or b or c // In all three cases n decreases by 1. int res = countStrUtil(dp, n - 1 , bCount, cCount); res += countStrUtil(dp, n - 1 , bCount - 1 , cCount); res += countStrUtil(dp, n - 1 , bCount, cCount - 1 ); return (dp[n][bCount][cCount] = res); } // A wrapper over countStrUtil() static int countStr( int n, int bCount, int cCount) { int [][][] dp = new int [n + 1 ][ 2 ][ 3 ]; for ( int i = 0 ; i < n + 1 ; i++) { for ( int j = 0 ; j < 2 ; j++) { for ( int k = 0 ; k < 3 ; k++) { dp[i][j][k] = - 1 ; } } } return countStrUtil(dp, n,bCount,cCount); } // Driver code public static void main(String[] args) { int n = 3 ; // Total number of characters int bCount = 1 , cCount = 2 ; System.out.println(countStr(n,bCount,cCount)); } } // This code has been contributed by 29AjayKumar |
Python3
# Python 3 program to count number of strings # of n characters with # n is total number of characters. # bCount and cCount are counts of 'b' # and 'c' respectively. def countStrUtil(dp, n, bCount = 1 ,cCount = 2 ): # Base cases if (bCount < 0 or cCount < 0 ): return 0 if (n = = 0 ): return 1 if (bCount = = 0 and cCount = = 0 ): return 1 # if we had saw this combination previously if (dp[n][bCount][cCount] ! = - 1 ): return dp[n][bCount][cCount] # Three cases, we choose, a or b or c # In all three cases n decreases by 1. res = countStrUtil(dp, n - 1 , bCount, cCount) res + = countStrUtil(dp, n - 1 , bCount - 1 , cCount) res + = countStrUtil(dp, n - 1 , bCount, cCount - 1 ) dp[n][bCount][cCount] = res return dp[n][bCount][cCount] # A wrapper over countStrUtil() def countStr(n): dp = [ [ [ - 1 for x in range ( 2 + 1 )] for y in range ( 1 + 1 )] for z in range (n + 1 )] return countStrUtil(dp, n) # Driver code if __name__ = = "__main__" : n = 3 # Total number of characters print (countStr(n)) # This code is contributed by chitranayal |
C#
// C# program to count number of strings // of n characters with using System; class GFG { // n is total number of characters. // bCount and cCount are counts of 'b' // and 'c' respectively. static int countStrUtil( int [,,] dp, int n, int bCount=1, int cCount=2) { // Base cases if (bCount < 0 || cCount < 0) return 0; if (n == 0) return 1; if (bCount == 0 && cCount == 0) return 1; // if we had saw this combination previously if (dp[n,bCount,cCount] != -1) return dp[n,bCount,cCount]; // Three cases, we choose, a or b or c // In all three cases n decreases by 1. int res = countStrUtil(dp, n - 1, bCount, cCount); res += countStrUtil(dp, n - 1, bCount - 1, cCount); res += countStrUtil(dp, n - 1, bCount, cCount - 1); return (dp[n, bCount, cCount] = res); } // A wrapper over countStrUtil() static int countStr( int n) { int [,,] dp = new int [n + 1, 2, 3]; for ( int i = 0; i < n + 1; i++) for ( int j = 0; j < 2; j++) for ( int k = 0; k < 3; k++) dp[i, j, k] = -1; return countStrUtil(dp, n); } // Driver code static void Main() { int n = 3; // Total number of characters Console.Write(countStr(n)); } } // This code is contributed by DrRoot_ |
Javascript
<script> // javascript program to count number of strings // of n characters with // n is total number of characters. // bCount and cCount are counts of 'b' // and 'c' respectively. function countStrUtil(dp , n, bCount , cCount) { // Base cases if (bCount < 0 || cCount < 0) { return 0; } if (n == 0) { return 1; } if (bCount == 0 && cCount == 0) { return 1; } // if we had saw this combination previously if (dp[n][bCount][cCount] != -1) { return dp[n][bCount][cCount]; } // Three cases, we choose, a or b or c // In all three cases n decreases by 1. var res = countStrUtil(dp, n - 1, bCount, cCount); res += countStrUtil(dp, n - 1, bCount - 1, cCount); res += countStrUtil(dp, n - 1, bCount, cCount - 1); return (dp[n][bCount][cCount] = res); } // A wrapper over countStrUtil() function countStr(n , bCount , cCount) { dp = Array(n+1).fill(0).map (x => Array(2).fill(0).map (x => Array(3).fill(0))); for (i = 0; i < n + 1; i++) { for (j = 0; j < 2; j++) { for (k = 0; k < 3; k++) { dp[i][j][k] = -1; } } } return countStrUtil(dp, n,bCount,cCount); } // Driver code var n = 3; // Total number of characters var bCount = 1, cCount = 2; document.write(countStr(n,bCount,cCount)); // This code contributed by shikhasingrajput </script> |
19
Time Complexity : O(n)
Auxiliary Space : O(n)
Thanks to Mr. Lazy for suggesting above solutions.
A solution that works in O(1) time :
We can apply the concepts of combinatorics to solve this problem in constant time. we may recall the formula that the number of ways we can arrange a total of n objects, out of which p number of objects are of one type, q objects are of another type, and r objects are of the third type is n!/(p!q!r!)
Let us proceed towards the solution step by step.
How many strings we can form with no ‘b’ and ‘c’? The answer is 1 because we can arrange a string consisting of only ‘a’ in one way only and the string would be aaaa….(n times).
How many strings we can form with one ‘b’? The answer is n because we can arrange a string consisting (n-1) ‘a’s and 1 ‘b’ is n!/(n-1)! = n . The same goes for ‘c’ .
How many strings we can form with 2 places, filled up by ‘b’ and/or ‘c’ ? Answer is n*(n-1) + n*(n-1)/2 . Because that 2 places can be either 1 ‘b’ and 1 ‘c’ or 2 ‘c’ according to our given constraints. For the first case, total number of arrangements is n!/(n-2)! = n*(n-1) and for second case that is n!/(2!(n-2)!) = n*(n-1)/2 .
Finally, how many strings we can form with 3 places, filled up by ‘b’ and/or ‘c’ ? Answer is (n-2)*(n-1)*n/2 . Because those 3 places can only be consisting of 1 ‘b’ and 2’c’ according to our given constraints. So, total number of arrangements is n!/(2!(n-3)!) = (n-2)*(n-1)*n/2 .
Implementation:
C++
// A O(1) CPP program to find number of strings // that can be made under given constraints. #include<bits/stdc++.h> using namespace std; int countStr( int n){ int count = 0; if (n>=1){ //aaa... count += 1; //b...aaa... count += n; //c...aaa... count += n; if (n>=2){ //bc...aaa... count += n*(n-1); //cc...aaa... count += n*(n-1)/2; if (n>=3){ //bcc...aaa... count += (n-2)*(n-1)*n/2; } } } return count; } // Driver code int main() { int n = 3; cout << countStr(n); return 0; } |
Java
// A O(1) Java program to // find number of strings // that can be made under // given constraints. import java.io.*; class GFG { static int countStr( int n) { return 1 + (n * 2 ) + (n * ((n * n) - 1 ) / 2 ); } // Driver code public static void main (String[] args) { int n = 3 ; System.out.println( countStr(n)); } } // This code is contributed by ajit |
Python 3
# A O(1) Python3 program to find # number of strings that can be # made under given constraints. def countStr(n): return ( 1 + (n * 2 ) + (n * ((n * n) - 1 ) / / 2 )) # Driver code if __name__ = = "__main__" : n = 3 print (countStr(n)) # This code is contributed # by ChitraNayal |
C#
// A O(1) C# program to // find number of strings // that can be made under // given constraints. using System; class GFG { static int countStr( int n) { return 1 + (n * 2) + (n * ((n * n) - 1) / 2); } // Driver code static public void Main () { int n = 3; Console.WriteLine(countStr(n)); } } // This code is contributed by m_kit |
PHP
<?php // A O(1) PHP program to find // number of strings that can // be made under given constraints. function countStr( $n ) { return 1 + ( $n * 2) + ( $n * (( $n * $n ) - 1) / 2); } // Driver code $n = 3; echo countStr( $n ); // This code is contributed by aj_36 ?> |
Javascript
<script> // A O(1) javascript program to // find number of strings // that can be made under // given constraints. function countStr(n) { return 1 + (n * 2) + (n * ((n * n) - 1) / 2); } // Driver code var n = 3; document.write(countStr(n)); // This code is contributed by Princi Singh </script> |
19
Time Complexity : O(1)
Auxiliary Space : O(1)
Thanks to Niharika Sahai for providing above solution.
Contact Us