Just like Ninja is incomplete without coding, programming is incomplete without recursion and hashmaps. Today we will see one such question in which these two topics are combined together.

We will understand this by the problem frequently asked in big companies, i.e.,

‘Maximize Cost of Forming a Set of Words Using Given Set of Characters’. Let’s discuss the problem in detail.

We have been given an arrayARR that has 'N' strings inside it. We have also been given another array, 'LET', which consists of 'M' characters(lowercase) along with the array 'TOTAL', which stores the cost of any ith English alphabet. Our task is to find the maximum cost( score ) of any valid set of words formed from using the letters which are given to us in such a way that it can be used only once, and each word ARR[i] can be formed at most once.

Things will become more clear from the following example.

Explanation: We can see that out of the given words, the only word that can be formed from the letters given in the 'LET' array is "dad". We can see from the 'TOTAL' array that the value of 'd' is 4, and the value of 'a' is 1. Thus total value is 4 + 1 + 4 = 9.

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

Brute Force Intuition

First, we will create all the subsets which are possible for the given ‘ARR,’ and we will check if there is any subset whose all strings can be formed by letters given to us, if yes then we will find the cost of that particular subset from the ‘TOTAL’ array. You can check out this blog to learn more about creating subsets of an array.

Once you have the subsets rest of the part is very straightforward, which can be understood by the code given below.

Code

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
int helper(vector<string> arr, int st,
vector<int> frequency, vector<int> total)
{
int n = arr.size();
// If we have Traversed the complete array.
if (st == n)
return 0;
int score = 0;
// Word score.
int total_score = 0;
// Copy of the frequency array.
vector<int> copyArray = frequency;
// Traverse the current word.
for (int i = 0; i < arr[st].size();
++i)
{
// Checking frequency of current character.
int idx = arr[st][i] - 'a';
// If frequency is 0.
if (copyArray[idx] == 0)
{
total_score = -1;
break;
}
// Adding to our total score.
total_score += total[idx];
// frequency from the original array is reduced now.
copyArray[idx]--;
}
// Calling for next index.
if (total_score > 0)
score = helper(arr, st + 1, copyArray, total) + total_score;
// If we include the word.
score = max( score, helper(arr, st + 1, frequency, total));
// Return the maximum score
return score;
}
// This function will return value of score which is maximum.
int maximumScore(vector<string> arr, vector < char>
let,
vector<int> total)
{
// For storing the frequency.
vector<int> frequency(26, 0);
for (char i = 0; i<
let.size(); i++)
frequency[let[i] - 'a']++;
// Maximum cost.
return helper(arr, 0, frequency, total);
}
// Driver Code
int main()
{
vector<string> arr = { "dad", "daddy", "xyz" };
vector < char> let = { 'a', 'b', 'c', 'd', 'e', 'd', 'x' };
vector<int> total = { 1, 2, 3, 4, 0, 0, 3, 0, 0, 0, 0, 0, 0,
0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
};
// Function Call
cout << (maximumScore(arr,let, total));
}

Output

9

Time Complexity

Time Complexity: O(2 ^ N)

here 'N' is array's length 'ARR'.

As at every step, we have two options to either include that element in our final answer or not, and since each function call calls itself twice unless it has been recursed 'N' times.

Thus the overall time complexity is O(2 ^ N).

Space Complexity

Space Complexity: O(N)

here ‘N’ is the length of the array ‘ARR’.

This is the space used by the recursion stack.

Approach 2: Using Memoization

We see that the time complexity is exponential, and we surely want to reduce it. We can see that there are many overlapping problems. Thus instead of calculating the same problems, again and again, we should think of memoizing them. We will use a Hashmap for it. Let's look at the code for a better understanding.

#include <iostream>
#include <vector>
#include <string>
#include <map>
using namespace std;
map<string, int> memo;
int helper(vector<string> arr, int st,
vector<int> frequency, vector<int> total)
{
int n = arr.size();
// If we have Traversed the complete array.
if (st == n)
return 0;
int score = 0;
// Word score.
int total_score = 0;
// Creating specific key for every string.
string key = "";
for (int i = 0; i < 26; ++i)
key = key + (char) frequency[i];
// Append the index
key = key + ", ";
key = key + (char) st;
if (memo.find(key) != memo.end())
return memo[key];
// Copy of the frequency array.
vector<int> copyArray = frequency;
// Traverse the current word.
for (int i = 0; i < arr[st].size();
++i)
{
// Checking frequency of current character.
int idx = arr[st][i] - 'a';
// If frequency is 0.
if (copyArray[idx] == 0)
{
total_score = -1;
break;
}
// Adding to our total score.
total_score += total[idx];
// frequency from the original array is reduced now.
copyArray[idx]--;
}
// Calling for next index.
if (total_score > 0)
score = helper(arr, st + 1, copyArray, total) + total_score;
// If we include the word.
score = max(score, helper(arr, st + 1, frequency, total));
// Return the maximum score
memo[key] = score;
return score;
}
// This will return the maximum score.
int maxScoreWords(vector<string> arr, vector < char>
let,
vector<int> total)
{
// For storing the frequency.
vector<int> frequency(26, 0);
for (char i = 0; i<
let.size(); i++)
frequency[let[i] - 'a']++;
// Maximum cost.
return helper(arr, 0, frequency, total);
}
// Driver Code
int main()
{
vector<string> arr = { "dad", "daddy", "xyz" };
vector < char>
let = { 'a', 'b', 'c', 'd', 'e', 'd', 'x' };
vector<int> total = { 1, 2, 3, 4, 0, 0, 3, 0, 0, 0, 0, 0, 0,
0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
};
// Function Call
cout << (maxScoreWords(arr,
let, total));
}

Output

9

Time Complexity

Time Complexity: O( N * L)

where where ‘N’ is the array ‘ARR’ s length and ‘L’ is the length of the longest word present in the ‘ARR’.

As of now, we are calculating the answer for every string only once. Therefore, it will cost us O(N) time. During calculation, we have to iterate over the word, which in the worst case would cost O(L) .

HashMap is similar to HashTable, but it does not have synchronization. It also allows storage of null keys, but there should only be one null key object and any number of null values. The order of the map is not guaranteed by this class.

What's the difference between a Hashtable and a HashMap?

The main distinction between Hashtable and HashMap is that HashMap can have one null key and any number of null values, whereas Hashtable does not. Hashtable and HashMap are synchronized, but HashMap is not. Due to the fact that HashMap is not synchronized, it is faster than Hashtable.

If you try to store a duplicate key in the HashMap, what will happen?

If you try to store a key that already exists in the HashMap, the old value will be overwritten by the new value. There will be no errors or exceptions. The HashMap's size remains constant. This is one of the reasons that when you call HashMap's keySet() method to get all keys, it returns Set rather than Collection because Set does not allow duplicates.

What is the Load Factor?

The load factor is a measurement of how full a hash table can get before its capacity is increased automatically. The hash table is rehashed (internal data structures are rebuilt) when the number of entries in the hash table exceeds the product of the load factor and the current capacity.

Are there any other Data Structures and Algorithms content in Coding Ninjas Studio?

Yes, Coding Ninjas Studio allows you to practice coding as well as answer frequently asked interview questions. The more we practice, the more likely we are to acquire a job at our dream company.

Conclusion

We saw how we could solve the problem, ‘Maximize Cost of Forming a Set of Words Using Given Set of Characters’ by both Naive as well as efficient methods, namely Dynamic programming. You must be thrilled about learning a new concept but the road to become a champ coder is still very long. So head over to our practice platform Coding Ninjas Studio to practice top problems on every topic, read interview experiences, and many more. Till then, Happy Coding!