Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Brute Force Intuition
4.
Code
4.1.
Time Complexity
4.2.
Space Complexity
5.
Approach 2: Using Memoization
5.1.
Time Complexity
5.2.
Space Complexity
6.
Frequently Asked Questions
6.1.
What is Hashmap?
6.2.
What's the difference between a Hashtable and a HashMap?
6.3.
If you try to store a duplicate key in the HashMap, what will happen?
6.4.
What is the Load Factor?
6.5.
Are there any other Data Structures and Algorithms content in Coding Ninjas Studio?
7.
Conclusion
Last Updated: Mar 27, 2024
Easy

Maximize Cost of Forming a Set of Words Using Given Set of Characters

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

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.

Problem Statement

Recommended topic about, kth largest element in an array, and Euclid GCD Algorithm

Problem Statement

We have been given an array  ARR 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.

ARR = { "dad", "daddy","xyz" }
LET = { 'a', 'b', 'c', 'd', 'e','d', 'x' }
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 }

 

Output

9

 

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.

Brute Force Intuition
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. 

Brute Force

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 and Space Complexity

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

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 and Space Complexity

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

Space Complexity

Space Complexity: O(N)

where ‘N’ is array ‘ARR’s length.

This is the space used by the recursion stack.

Check out this problem - Find Duplicate In Array

Frequently Asked Questions

What is Hashmap?

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!

Previous article
C++ Program To Print All Permutations Of A Given String
Next article
Print all unique paths from a given source to destination in a Matrix moving only down or right
Live masterclass