Count of strings that can be formed using a, b and c under given constraints - GeeksforGeeks

Count of strings that can be formed using a, b and c under given constraints - GeeksforGeeks
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.

A simple solution is to recursively count all possible combination of string that can be mode up to latter ‘a’, ‘b’, and ‘c’.

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;

}

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.

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

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);

}

Read full article from Count of strings that can be formed using a, b and c under given constraints - GeeksforGeeks