Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Example
2.
Approach
2.1.
PseudoCode
3.
Implementation in C++
3.1.
Complexity Analysis
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024

Least count of words required to construct a target String

Author Urwashi Priya
1 upvote

Introduction

In this blog, we will discuss a backtracking problem asked frequently in Interviews.

Problem Statement

The problem is to find Least count of words required to construct a target String.

We are given an array of words and a target string. Assuming all letters in a string are infinitely available, we need to construct our target string and we need to find the minimum number of words included in the construction of a target string.

Sample Example

Example: Say we have an array of words given as: ‘with’, ‘example’, ‘science’ and the target string is ‘thehat’. 

‘thehat’ consists of 2 ‘t’, 2 ‘h’, 1 ‘e’, 1 ‘a’.

We require 2 times with for t and h

And 1-time example for e and a.

So 3 will be returned as our answer.

Approach

The approach to find the Least count of words required to construct a target String can be explained by the backtracking method.

In our example, we have 2 X 3 matrix. Source = 0,0 and Destination = 1,2.

If the optimal solution is present there, then return.

Update the count for all letters.

if the target has been constructed, update and return.

Check if the target can be constructed or not.

Return true or false accordingly

Check for the next position if true.

Else check for the next index.

There are 26 alphabets. Each alphabet has two possibilities. therefore, time complexity would be O(M*26*2^N) and the space complexity would be O(M*26).

Till now, I assume you must have got the basic idea of what has been asked in the problem statement. So, I strongly recommend you first give it a try.

try here

Please have a look at the algorithm, and then again, you must give it a try.

PseudoCode

Algorithm

___________________________________________________________________

procedure fun(ll ind, vector<ll> &cur, ll step, vector<ll> &target, vector<vector<ll>> &arr):

___________________________________________________________________

1.  c = 0
2.  for(int i=0;i<26;i++):
3.       if (i == d[0] && j == d[1]):
              if(tmp[i]+arr[ind][i]>target[i]): return
              if(cur[i]==target[i]): c++
4.  if(c==26): 
          ans = min(ans, step)
          Return
5.  if(ind == arr.size()): return
6.  vector<ll> tmp = cur;
     bool f = false;
7.  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
8.  if(f):
         fun(ind, tmp, step+1, target, arr)
9.  fun(ind+1, cur, step, target, arr)

end procedure

___________________________________________________________________

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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

 

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.

Live masterclass