Lexicographically largest string possible for a given cost of appending characters

Namachila November 19, 2025

0 0 7 minutes read

Given an integer W and an array a[] of size 26 where a_idenotes the cost of using the i^thalphabet, 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 = 236

Input: 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 possible
bool 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 generated
void 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 approach
import java.util.*;
class GFG{
 
// Function to find the 
// lexicographically largest 
// String possible
static 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 generated
static 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 code
public 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 possible
def 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 generated
def 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 code
if __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 approach
using System;
using System.Collections.Generic;
class GFG{
 
// Function to find the 
// lexicographically largest 
// String possible
static 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 generated
static 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 code
public 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(2²⁶⁾
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 zambiatek!