Given an integer W and an array a[] of size 26 where ai denotes the cost of using the ith alphabet, the task is to find lexicographically the largest string that can be generated for a cost, W.
Examples:
Input: W = 236, a[] = {1, 1, 2, 33, 4, 6, 9, 7, 36, 32, 58, 32, 28, 904, 22, 255, 47, 69, 558, 544, 21, 36, 48, 85, 48, 58}
Output: zzzze
Explanation:
4 * (cost of z) + cost of e = 4 * 58 + 4 = 232 + 4 = 236Input: W = 6674, a[] = {252, 288, 578, 746, 295, 884, 198, 655, 503, 868, 942, 506, 718, 498, 727, 338, 43, 768, 783, 312, 369, 712, 230, 106, 102, 554}
Output: zzzzzzzzzzzyyyyqqqq
Explanation:
11 * (cost of z) + 4 * (cost of y) + 4 * (cost of q) = 11 * 554 + 4 * 102 + 4 * 43 = 6094 + 408 + 172 = 6674
Approach: The idea is to iterate over the array a[] from the characters ‘z‘ to ‘a‘ alphabets. Now, find a combination in a[] where the sum is equal to W. The same repeated number may be chosen from a[] an unlimited number of times. Then, use recursion and backtracking to solve the problem. Follow the steps below to solve the problem:
- For the subproblem sum = 0 at any instant, print the string obtained as the cost of the characters stored in the array till now sums up to W and since the string has been generated appending characters starting from ‘z‘, the string thus formed is the lexicographically the largest string.
- Otherwise, if the sum is negative or index < 0, return false for these subproblems.
- Otherwise, find lexicographically the largest string possible by including as well as excluding the current character in the resultant string.
- Print lexicographically the largest string obtained by completing the above steps.
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to find the // lexicographically largest // String possiblebool lexi_largest_String(int a[], int i, int sum, vector<int> &v){ // If sum is less than 0 if (sum < 0) return false; // If sum is equal to 0 if (sum == 0) return true; // If sum is less than 0 if (i < 0) return false; // Add current character v.push_back(i); // Check if selecting current // character generates // lexicographically largest String if (lexi_largest_String(a, i, sum - a[i], v)) return true; // Backtrack if solution // not found auto it = v.end(); it--; v.erase(it); // Find the lexicographically // largest String excluding // the current character return lexi_largest_String(a, i - 1, sum, v);} // Function to print the // lexicographically largest // String generatedvoid generateString(int a[], int sum){ vector<int> v; // Function call lexi_largest_String(a, 25, sum, v); // Stores the String string s = ""; for (int j = 0; j < v.size(); j++) s += (char)(v[j] + 'a'); // Print the lexicographically // largest String formed cout << s << endl;}// Driver code int main(){ // Cost of adding each // alphabet int a[] = {1, 1, 2, 33, 4, 6, 9, 7, 36, 32, 58, 32, 28, 904, 22, 255, 47, 69, 558, 544, 21, 36, 48, 85, 48, 58}; // Cost of generating // the String int sum = 236; generateString(a, sum); return 0;}// This code is contributed by divyeshrabadiya07 |
Java
// Java Program to implement// the above approachimport java.util.*;class GFG{// Function to find the // lexicographically largest // String possiblestatic boolean lexi_largest_String(int a[], int i, int sum, Vector<Integer> v){ // If sum is less than 0 if (sum < 0) return false; // If sum is equal to 0 if (sum == 0) return true; // If sum is less than 0 if (i < 0) return false; // Add current character v.add(i); // Check if selecting current // character generates // lexicographically largest String if (lexi_largest_String(a, i, sum - a[i], v)) return true; // Backtrack if solution // not found v.remove(v.size() - 1); // Find the lexicographically // largest String excluding // the current character return lexi_largest_String(a, i - 1, sum, v);}// Function to print the // lexicographically largest // String generatedstatic void generateString(int a[], int sum){ Vector<Integer> v = new Vector<Integer>(); // Function call lexi_largest_String(a, 25, sum, v); // Stores the String String s = ""; for (int j = 0; j < v.size(); j++) s += (char)(v.get(j) + 'a'); // Print the lexicographically // largest String formed System.out.print(s + "\n");}// Driver codepublic static void main(String[] args){ // Cost of adding each alphabet int a[] = {1, 1, 2, 33, 4, 6, 9, 7, 36, 32, 58, 32, 28, 904, 22, 255, 47, 69, 558, 544, 21, 36, 48, 85, 48, 58}; // Cost of generating // the String int sum = 236; generateString(a, sum);}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program to implement# the above approach# Function to find the lexicographically# largest string possibledef lexi_largest_string(a, i, sum, v): # If sum is less than 0 if (sum < 0): return False # If sum is equal to 0 if (sum == 0): return True # If sum is less than 0 if (i < 0): return False # Add current character v.append(i) # Check if selecting current character # generates lexicographically # largest string if(lexi_largest_string(a, i, sum - a[i], v)): return True # Backtrack if solution not found v.pop(-1) # Find the lexicographically # largest string excluding # the current character return lexi_largest_string(a, i - 1, sum, v)# Function to print the lexicographically# largest string generateddef generateString(a, sum): v = [] # Function call lexi_largest_string(a, 25, sum , v) # Stores the string s = "" for j in range(len(v)): s += chr(v[j] + ord('a')) # Print the lexicographically # largest string formed print(s)# Driver codeif __name__ == '__main__': a = [ 1, 1, 2, 33, 4, 6, 9, 7, 36, 32, 58, 32, 28, 904, 22, 255, 47, 69, 558, 544, 21, 36, 48, 85, 48, 58 ] # Cost of generating # the string sum = 236 generateString(a, sum)# This code is contributed by Shivam Singh |
C#
// C# Program to implement// the above approachusing System;using System.Collections.Generic;class GFG{// Function to find the // lexicographically largest // String possiblestatic bool lexi_largest_String(int []a, int i, int sum, List<int> v){ // If sum is less than 0 if (sum < 0) return false; // If sum is equal to 0 if (sum == 0) return true; // If sum is less than 0 if (i < 0) return false; // Add current character v.Add(i); // Check if selecting current // character generates // lexicographically largest String if (lexi_largest_String(a, i, sum - a[i], v)) return true; // Backtrack if solution // not found v.RemoveAt(v.Count - 1); // Find the lexicographically // largest String excluding // the current character return lexi_largest_String(a, i - 1, sum, v);}// Function to print the // lexicographically largest // String generatedstatic void generateString(int []a, int sum){ List<int> v = new List<int>(); // Function call lexi_largest_String(a, 25, sum, v); // Stores the String String s = ""; for (int j = 0; j < v.Count; j++) s += (char)(v[j] + 'a'); // Print the lexicographically // largest String formed Console.Write(s + "\n");}// Driver codepublic static void Main(String[] args){ // Cost of adding each alphabet int []a = {1, 1, 2, 33, 4, 6, 9, 7, 36, 32, 58, 32, 28, 904, 22, 255, 47, 69, 558, 544, 21, 36, 48, 85, 48, 58}; // Cost of generating // the String int sum = 236; generateString(a, sum);}}// This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript Program to implement the above approach // Function to find the // lexicographically largest // String possible function lexi_largest_String(a, i, sum, v) { // If sum is less than 0 if (sum < 0) return false; // If sum is equal to 0 if (sum == 0) return true; // If sum is less than 0 if (i < 0) return false; // Add current character v.push(i); // Check if selecting current // character generates // lexicographically largest String if (lexi_largest_String(a, i, sum - a[i], v)) return true; // Backtrack if solution // not found v.pop(); // Find the lexicographically // largest String excluding // the current character return lexi_largest_String(a, i - 1, sum, v); } // Function to print the // lexicographically largest // String generated function generateString(a, sum) { let v = []; // Function call lexi_largest_String(a, 25, sum, v); // Stores the String let s = ""; for (let j = 0; j < v.length; j++) s += String.fromCharCode(v[j] + 'a'.charCodeAt()); // Print the lexicographically // largest String formed document.write(s + "</br>"); } // Cost of adding each alphabet let a = [1, 1, 2, 33, 4, 6, 9, 7, 36, 32, 58, 32, 28, 904, 22, 255, 47, 69, 558, 544, 21, 36, 48, 85, 48, 58]; // Cost of generating // the String let sum = 236; generateString(a, sum);</script> |
Output
zzzze
Time Complexity: O(226)
Auxiliary Space: O(N)
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!
