## 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.

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**

___________________________________________________________________