String lexicográficamente más grande posible por un costo dado de agregar caracteres

Posted on by Rudeus Greyrat

Dado un entero W y una array a[] de tamaño 26 donde ai denota el costo de usar el i -ésimo alfabeto, la tarea es encontrar lexicográficamente la string más grande que se puede generar por un costo , W.

Ejemplos:

Entrada: 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}
Salida: zzzze 
Explicación: 
4 * (coste de z) + coste de e = 4 * 58 + 4 = 232 + 4 = 236

Entrada: 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}
Salida: zzzzzzzzzzzyyyyqqqq 
Explicación: 
11 * (costo de z) + 4 * (costo de y) + 4 * (costo de q) = 11 * 554 + 4 * 102 + 4 * 43 = 6094 + 408 + 172 = 6674

Enfoque: La idea es iterar sobre la array a[] desde los caracteres ‘ z ‘ hasta los alfabetos ‘ a ‘. Ahora, encuentre una combinación en a[] donde la suma sea igual a W . El mismo número repetido se puede elegir de un [] un número ilimitado de veces. Luego, use la recursividad y el retroceso para resolver el problema. Siga los pasos a continuación para resolver el problema:

  • Para el subproblema sum = 0 en cualquier instante, imprima la string obtenida como el costo de los caracteres almacenados en la array hasta ahora suma W y como la string se ha generado agregando caracteres a partir de ‘ z ‘, la string así formada es la lexicográficamente la string más grande .
  • De lo contrario, si la suma es negativa o el índice < 0, devuelve falso para estos subproblemas.
  • De lo contrario, encuentre lexicográficamente la string más grande posible incluyendo y excluyendo el carácter actual en la string resultante.
  • Imprima lexicográficamente la string más grande obtenida al completar los pasos anteriores.

A continuación se muestra la implementación del enfoque anterior:

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>
Producción

zzzze

Complejidad temporal: O(2 26) 
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por man_preet y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *