Least count of words required to construct a target String

Implementation in C++

// C++ program to find the Least count of words required to construct a target String
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll ans;

void fun(ll ind, vector<ll> &cur, ll step, vector<ll> &target, vector<vector<ll>> &arr)
{
    ll c = 0;
    for (int i = 0; i < 26; i++)
    {
        if (cur[i] > target[i])
            return;
        // updating the count for all letters.
        if (cur[i] == target[i])
            c++;
    }

    // if target has been constructed update and return.
    if (c == 26)
    {
        ans = min(ans, step);
        return;
    }
    if (ind == arr.size())
        return;

    vector<ll> tmp = cur;
    bool f = false;
    for (int i = 0; i < 26; i++)
    {
        if (tmp[i] + arr[ind][i] > target[i])
        {
            tmp[i] = target[i];
        }
        else
        {
            tmp[i] += arr[ind][i];
        }

        if (tmp[i] != cur[i])
            f = true;
    }
    if (f)
    {
        fun(ind, tmp, step + 1, target, arr);
    }

    fun(ind + 1, cur, step, target, arr);
}

void solve()
{
    ll n;
    cin >> n;
    vector<vector<ll>> brr(n, vector<ll>(26));
    for (int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        for (auto y : s)
        {
            brr[i][y - 'a']++;
        }
    }
    string target;
    cin >> target;
    vector<ll> tar(26);
    for (auto x : target)
    {
        tar[x - 'a']++;
    }

    ans = LLONG_MAX;
    vector<ll> cur(26);
    fun(0, cur, 0, tar, brr);
    if (ans == LLONG_MAX)
    {
        cout << -1 << endl;
    }
    else
    {
        cout << ans << endl;
    }
}

int main()
{
    solve();
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Sample Input: 
3
with
example
science
thehat

Sample Output:
3

Complexity Analysis

Time Complexity: O(M*26*2^N)

Analysing Time Complexity:

There are 26 alphabets. Each alphabet has two possibilities.

Space complexity: O(M*26)

Also see, Euclid GCD Algorithm

FAQs

1. Is a long data type the same as an int data type?
   No, long is 64 bits in size whereas int is 32 bits in size.
    
2. Are backtracking and recursion the same? 
   In the recursion, the function is used to call itself until it reaches a base case. In backtracking, we use recursion to explore all the possible possibilities until we get the best result for the problem
    
3. List the difference between backtracking and dynamic programming?
   Dynamic programming always gives the optimal solutions, even the subproblems are based on the principle of optimality but this is not the case of backtracking. Furthermore, dynamic programming is based on the concept of dividing complex problems into simple ones whereas backtracking is based on the concept of building many problems recursively and then omitting the ones not satisfying the constraints.

Key Takeaways

This article taught us how to Least count of words required to construct a target String by approaching the problem using recursion and backtracking. We discussed its implementation using illustrations, pseudocode, and then proper code.

We hope you could take away critical techniques like analyzing problems by walking over the execution of the examples and finding out the recursive pattern followed.

Now, we recommend you practice problem sets based on recursion to master your fundamentals. You can get a wide range of questions similar to this on Coding Ninjas Studio. 

Check out this problem - Frog Jump

It's not the end. Must solve the problem of similar types. 

Happy Coding.