Tutorialspoint.dev

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 combination of string that can be mode up to latter ‘a’, ‘b’, and ‘c’.



Below is implementation of 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
?>


Output :

19

Time complexity of above solution is exponential.

 

Efficient Solution
If we drown a recursion tree of above code, we can notice that same values appear multiple times. So we store results which 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

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_


Output :

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 :

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)
{
    return 1+(n*2)+(n*((n*n)-1)/2);
}
  
// 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
?>


Output :



19

Time Complexity : O(1)
Auxiliary Space : O(1)

Thanks to Niharika Sahai for providing above solution.

Reference :
https://careercup.appspot.com/question?id=5717453712654336

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter