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!
