Given an array of strings, words[] of size M and a string target of size N. The task is to find the minimum number of words required to spell out the string target by cutting individual letters from the collection of words and rearranging them, provided that there are infinite supplies of each word. If it is not possible, print -1.
Examples:
Input: words[] = {“with”, “example”, “science”}, target = “thehat”
Output: 3
Explanation: The target string, “thehat” consists of {‘h’ = 2, ‘t’ = 2, ‘e’ = 1, ‘a’ = 1}.
The two “with” strings are required to get two ‘h’ and two ‘t’ and one “example” string is required to get one ‘e’ and one ‘a’ to form the target string “thehat”.
So, total word required to construct the given target is 3.Input: words[] = {“notice”, “possible”}, target = “basicbasic”
Output: -1
Explanation: It is not possible to form the given target string.
Approach: The idea is to use backtracking. Follow the steps to solve the problem:
- Declare a 2D array, say countMap[][], where countMap[i][j] stores the count of jth character in ith string.
- Declare an array charAvavilable[26], denoting the current count of available characters.
- Define a recursive function that takes in the current index, i (initially 0) of the string, target as the input.
- If the current count is greater than the overall count, then return. Also, if the current index, i is equal to N, update the overall count and return.
- If there is an occurrence of target[i] in charAvailable[],
- Decrement the occurrence of the character target[i] in charAvailable[].
- Recursively call for index i+1, simultaneously updating count by 1.
- Increment the occurrence of the character target[i] by 1 after the function call for backtracking.
- Otherwise, iterate the countMap[][] to find the occurrence of target[i]. If found then, recursively call the function by updating count by 1 and also perform the backtracking step after the function call.
- Print the minimum number of words required.
Below is the implementation of the above approach:
C++
// C++ program of the above approach#include <bits/stdc++.h>using namespace std;// countMap[][] to store// count of charactersvector<vector<int> > countMap;int cnt = INT_MAX;// Function to get minimum number of// stickers for a particular statevoid count(int curCnt, int pos, vector<int>charAvailable, string target, vector<string> stickers){ // If an optimal solution is // already there, return if (curCnt >= cnt) return; int m = stickers.size(); int n = target.size(); // If Target has been constructed // update cnt and return if (pos == n) { cnt = min(cnt, curCnt); return; } char c = target[pos]; if (charAvailable > 0) { // Update charAvailable[] charAvailable--; // Recursizevely function call // for (pos + 1) count(curCnt, pos + 1, charAvailable, target, stickers); // Update charAvailable[] charAvailable++; } else { for(int i = 0; i < m; i++) { if (countMap[i] == 0) continue; // Update charAvailable[] for(int j = 0; j < 26; j++) { charAvailable[j] += countMap[i][j]; } // Recursizeve Call count(curCnt + 1, pos, charAvailable, target, stickers); // Update charAvailable[] for(int j = 0; j < 26; j++) { charAvailable[j] -= countMap[i][j]; } } }}// Function to find the minimum// number of stickersint minStickers(vector<string> stickers, string target){ // Base Case if (target == "") return -1; if (target.size() == 0) return 0; if (stickers.size() == 0) return -1; int m = stickers.size(); countMap.resize(m, vector<int>(26, 0)); // Fill the countMap Array for(int i = 0; i < stickers.size(); i++) { string s = stickers[i]; for(char c : s) { countMap[i]++; } } // Recusizeve function call to get // minimum number of stickers vector<int> temp(26); count(0, 0, temp, target, stickers); return cnt == INT_MAX ? -1 : cnt;}// Driver Codeint main(){ // Given Input vector<string> str = {"with", "example", "science"}; string target = "thehat"; // Function Call int Result = minStickers(str, target); // Print the result cout << Result;}// This code is contributed by mohit kumar 29 |
Java
// Java program of the above approachimport java.io.*;import java.util.*;class Sol { // countMap[][] to store // count of characters int[][] countMap; int cnt = Integer.MAX_VALUE; // Function to find the minimum // number of stickers public int minStickers(String[] stickers , String target) { // Base Case if (target == null) return -1; if (target.length() == 0) return 0; if (stickers == null || stickers.length == 0) return -1; int m = stickers.length; countMap = new int[m][26]; // Fill the countMap Array for (int i = 0; i < stickers.length; i++) { String s = stickers[i]; for (char c : s.toCharArray()) { countMap[i]++; } } // Recursive function call to get // minimum number of stickers count(0, 0, new int[26], target, stickers); return cnt == Integer.MAX_VALUE ? -1 : cnt; } // Function to get minimum number of // stickers for a particular state private void count(int curCnt, int pos, int[] charAvailable, String target, String[] stickers) { // If an optimal solution is // already there, return if (curCnt >= cnt) return; int m = stickers.length; int n = target.length(); // If Target has been constructed // update cnt and return if (pos == n) { cnt = Math.min(cnt, curCnt); return; } char c = target.charAt(pos); if (charAvailable > 0) { // Update charAvailable[] charAvailable--; // Recursively function call // for (pos + 1) count(curCnt, pos + 1, charAvailable, target, stickers); // Update charAvailable[] charAvailable++; } else { for (int i = 0; i < m; i++) { if (countMap[i] == 0) continue; // Update charAvailable[] for (int j = 0; j < 26; j++) { charAvailable[j] += countMap[i][j]; } // Recursive Call count(curCnt + 1, pos, charAvailable, target, stickers); // Update charAvailable[] for (int j = 0; j < 26; j++) { charAvailable[j] -= countMap[i][j]; } } } }}class GFG { // Driver Code public static void main(String[] args) { Sol st = new Sol(); // Given Input String[] str = { "with", "example", "science" }; String target = "thehat"; // Function Call int Result = st.minStickers(str, target); // Print the result System.out.println(Result); }} |
Python3
# Python program of the above approachimport sys# countMap[][] to store count of characterscountMap = []cnt = sys.maxsize# Function to get minimum number of stickers for a particular statedef count(curCnt, pos, charAvailable, target, stickers): global cnt # If an optimal solution is already there, return if curCnt >= cnt: return m = len(stickers) n = len(target) # If Target has been constructed update cnt and return if pos == n: cnt = min(cnt, curCnt) return c = target[pos] if charAvailable[ord(c) - ord('a')] > 0: # Update charAvailable[] charAvailable[ord(c) - ord('a')] -= 1 # Recursizevely function call for (pos + 1) count(curCnt, pos + 1, charAvailable, target, stickers) # Update charAvailable[] charAvailable[ord(c) - ord('a')] += 1 else: for i in range(m): if countMap[i][ord(c) - ord('a')] == 0: continue # Update charAvailable[] for j in range(26): charAvailable[j] += countMap[i][j] # Recursizeve Call count(curCnt + 1, pos, charAvailable, target, stickers) # Update charAvailable[] for j in range(26): charAvailable[j] -= countMap[i][j]# Function to find the minimum number of stickersdef minStickers(stickers, target): global cnt # Base Case if target == "": return -1 if len(target) == 0: return 0 if len(stickers) == 0: return -1 m = len(stickers) global countMap countMap = [[0]*26 for _ in range(m)] # Fill the countMap Array for i in range(m): s = stickers[i] for c in s: countMap[i][ord(c) - ord('a')] += 1 # Recusizeve function call to get minimum number of stickers temp = [0]*26 count(0, 0, temp, target, stickers) return cnt if cnt != sys.maxsize else -1# Driver Codeif __name__ == "__main__": # Given Input str = ["with", "example", "science"] target = "thehat" # Function Call Result = minStickers(str, target) # Print the result print(Result) # This code is contributed by rutikbhosale |
C#
// C# program of the above approachusing System;using System.Collections.Generic;public class Program { // countMap[][] to store // count of characters static List<List<int> > countMap = new List<List<int> >(); static int cnt = int.MaxValue; // Function to get minimum number of // stickers for a particular state static void Count(int curCnt, int pos, List<int> charAvailable, string target, List<string> stickers) { // If an optimal solution is // already there, return if (curCnt >= cnt) return; int m = stickers.Count; int n = target.Length; // If Target has been constructed // update cnt and return if (pos == n) { cnt = Math.Min(cnt, curCnt); return; } char c = target[pos]; if (charAvailable > 0) { // Update charAvailable[] charAvailable--; // Recursizevely function call // for (pos + 1) Count(curCnt, pos + 1, charAvailable, target, stickers); // Update charAvailable[] charAvailable++; } else { for (int i = 0; i < m; i++) { if (countMap[i] == 0) continue; // Update charAvailable[] for (int j = 0; j < 26; j++) { charAvailable[j] += countMap[i][j]; } // Recursizeve Call Count(curCnt + 1, pos, charAvailable, target, stickers); // Update charAvailable[] for (int j = 0; j < 26; j++) { charAvailable[j] -= countMap[i][j]; } } } } // Function to find the minimum // number of stickers static int MinStickers(List<string> stickers, string target) { // Base Case if (target == "") return -1; if (target.Length == 0) return 0; if (stickers.Count == 0) return -1; int m = stickers.Count; countMap = new List<List<int> >(m); // Fill the countMap Array for (int i = 0; i < stickers.Count; i++) { string s = stickers[i]; countMap.Add(new List<int>(26)); for (int j = 0; j < 26; j++) { countMap[i].Add(0); } foreach(char c in s) { countMap[i]++; } } // Recusizeve function call to get // minimum number of stickers List<int> temp = new List<int>(26); for (int i = 0; i < 26; i++) { temp.Add(0); } Count(0, 0, temp, target, stickers); return cnt == int.MaxValue ? -1 : cnt; } // Driver Code public static void Main() { // Given Input List<string> str = new List<string>() { "with", "example", "science" }; string target = "thehat"; // Function Call int Result = MinStickers(str, target); // Print the result Console.WriteLine(Result); }}// This code is contributed by rutikbhosale |
Javascript
// JavaScript program of the above approach// countMap[][] to store count of characterslet countMap;let cnt = Number.MAX_SAFE_INTEGER;// Function to get minimum number of stickers for a particular statefunction count(curCnt, pos, charAvailable, target, stickers) {// If an optimal solution is already there, returnif (curCnt >= cnt) return;const m = stickers.length;const n = target.length;// If Target has been constructed update cnt and returnif (pos === n) { cnt = Math.min(cnt, curCnt); return;}const c = target[pos];if (charAvailable > 0) { // Update charAvailable[] charAvailable--; // Recursively function call for (pos + 1) count(curCnt, pos + 1, charAvailable, target, stickers); // Update charAvailable[] charAvailable++;} else { for(let i = 0; i < m; i++) { if (countMap[i] === 0) continue; // Update charAvailable[] for(let j = 0; j < 26; j++) { charAvailable[j] += countMap[i][j]; } // Recursively Call count(curCnt + 1, pos, charAvailable, target, stickers); // Update charAvailable[] for(let j = 0; j < 26; j++) { charAvailable[j] -= countMap[i][j]; } }}}// Function to find the minimum number of stickersfunction minStickers(stickers, target) {// Base Caseif (target === '') return -1;if (target.length === 0) return 0;if (stickers.length === 0) return -1;const m = stickers.length;countMap = new Array(m).fill().map(() => new Array(26).fill(0));// Fill the countMap Arrayfor(let i = 0; i < stickers.length; i++) { const s = stickers[i]; for(let j = 0; j < s.length; j++) { countMap[i][s.charCodeAt(j) - 'a'.charCodeAt()]++; }}// Recursively function call to get minimum number of stickersconst temp = new Array(26).fill(0);count(0, 0, temp, target, stickers);return cnt === Number.MAX_SAFE_INTEGER ? -1 : cnt;}// Driver Code// Given Inputconst str = ["with", "example", "science"];const target = "thehat";// Function Callconst Result = minStickers(str, target);// Print the resultconsole.log(Result);//This code is contributed by rutikbhosale |
Output:
3
Time Complexity: O(M*26*2N)
Auxiliary Space: O(M*26)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
