Minimice el costo de vaciar una string determinada eliminando caracteres alfabéticamente

Posted on by Rudeus Greyrat

Dada la string str , la tarea es minimizar el costo total para eliminar todos los caracteres de la string en orden alfabético .

El costo de eliminar cualquier carácter en el i -ésimo índice de la string será i . La indexación está basada en 1.

Ejemplos:

Entrada: str = “abcab” 
Salida: 8 
Explicación: 
Primero se elimina el carácter ‘a’ en el índice 1, str[] se convierte en “bcab”, 
luego se elimina el carácter ‘a’ con índice 3, str[] se convierte en “bcb” 
Después que se elimina el carácter ‘b’ con índice 1, str[] se convierte en «cb», 
luego se elimina el carácter ‘b’ con índice 2, str[] se convierte en «c», 
finalmente, se elimina el carácter ‘c’. 
Puntos totales = 1+3 + 1 + 2 + 1 = 8. 

Entrada: str = «def» 
Salida: 3

Enfoque ingenuo: el enfoque más simple es eliminar el carácter más pequeño con un índice más pequeño en la string en cada paso y seguir agregando el costo al costo total. Imprime el costo final después de esta operación.

Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)

Enfoque eficiente: el enfoque anterior se puede optimizar calculando previamente para cada carácter, la cantidad de caracteres más pequeños que lo preceden en la string dada. A continuación se muestran los pasos:

  1. Inicializar el costo total a 0 .
  2. Transverse la string dada y para cada carácter, cuente el número de caracteres que son menores que el carácter actual y que han ocurrido antes.
  3. Si este recuento es 0, significa que el carácter actual se eliminará en el índice actual, por lo tanto, agregue el índice del carácter al costo resultante.
  4. De lo contrario, reste el recuento de su índice actual y luego súmelo al costo total.
  5. Imprima el costo total después de todos los pasos anteriores.

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

C++

// C++ program for the above approach
#include <bits/stdc++.h>
#include <vector>
using namespace std;
  
// Function to find the minimum cost
// required to remove each character
// of the string in alphabetical order
int minSteps(string str, int N)
{
    int smaller, cost = 0;
  
    // Stores the frequency of
    // characters of the string
    int f[26] = { 0 };
  
    // Iterate through the string
    for (int i = 0; i < N; i++) {
        int curr_ele = str[i] - 'a';
        smaller = 0;
  
        // Count the number of characters
        // smaller than the present character
        for (int j = 0; j <= curr_ele; j++) {
            if (f[j])
                smaller += f[j];
        }
  
        // If no smaller character
        // precedes current character
        if (smaller == 0)
            cost += (i + 1);
        else
            cost += (i - smaller + 1);
  
        // Increase the frequency of
        // the current character
        f[str[i] - 'a']++;
    }
  
    // Return the
    // total cost
    return cost;
}
  
// Driver Code
int main()
{
    // Given string str
    string str = "abcab";
    int N = str.size();
  
    // Function call
    cout << minSteps(str, N);
    return 0;
}

Java

// Java program for 
// the above approach
import java.io.*;
class GFG{
  
    // Function to find the minimum cost
    // required to remove each character
    // of the string in alphabetical order
    static int minSteps(String str, int N)
    {
        int smaller, cost = 0;
  
        // Stores the frequency of
        // characters of the string
        int f[] = new int[26];
  
        // Iterate through the string
        for (int i = 0; i < N; i++) 
        {
            int curr_ele = str.charAt(i) - 'a';
            smaller = 0;
  
            // Count the number of characters
            // smaller than the present character
            for (int j = 0; j <= curr_ele; j++) 
            {
                if (f[j] != 0)
                    smaller += f[j];
            }
  
            // If no smaller character
            // precedes current character
            if (smaller == 0)
                cost += (i + 1);
            else
                cost += (i - smaller + 1);
  
            // Increase the frequency of
            // the current character
            f[str.charAt(i) - 'a']++;
        }
  
        // Return the
        // total cost
        return cost;
    }
  
    // Driver Code
    public static void main(String[] args)
    {
        // Given string str
        String str = "abcab";
  
        int N = str.length();
  
        // Function call
        System.out.println(minSteps(str, N));
    }
}
  
// This code is contributed by AnkitRai01

Python3

# Python3 program for the above approach 
  
# Function to find the minimum cost
# required to remove each character
# of the string in alphabetical order 
def minSteps(str, N):
  
    cost = 0
  
    # Stores the frequency of
    # characters of the string
    f = [0] * 26
  
    # Iterate through the string
    for i in range(N):
        curr_ele = ord(str[i]) - ord('a')
        smaller = 0
  
        # Count the number of characters
        # smaller than the present character
        for j in range(curr_ele + 1):
            if (f[j]):
                smaller += f[j]
  
        # If no smaller character
        # precedes current character
        if (smaller == 0):
            cost += (i + 1)
        else:
            cost += (i - smaller + 1)
  
        # Increase the frequency of
        # the current character
        f[ord(str[i]) - ord('a')] += 1
  
    # Return the total cost
    return cost
  
# Driver Code
  
# Given string str
str = "abcab"
  
N = len(str)
  
# Function call
print(minSteps(str, N))
  
# This code is contributed by Shivam Singh

C#

// C# program for 
// the above approach
using System;
class GFG{
  
// Function to find the minimum cost
// required to remove each character
// of the string in alphabetical order
static int minSteps(string str, int N)
{
    int smaller, cost = 0;
  
    // Stores the frequency of
    // characters of the string
    int[] f = new int[26];
  
    // Iterate through the string
    for (int i = 0; i < N; i++) 
    {
        int curr_ele = str[i] - 'a';
        smaller = 0;
  
        // Count the number of characters
        // smaller than the present character
        for (int j = 0; j <= curr_ele; j++) 
        {
            if (f[j] != 0)
            smaller += f[j];
        }
          
        // If no smaller character
        // precedes current character
        if (smaller == 0)
            cost += (i + 1);
        else
            cost += (i - smaller + 1);
  
        // Increase the frequency of
        // the current character
        f[str[i] - 'a']++;
    }
  
    // Return the
    // total cost
    return cost;
}
  
// Driver Code
public static void Main()
{
  
    // Given string str
    string str = "abcab";
  
    int N = str.Length;
  
    // Function call
    Console.Write(minSteps(str, N));
}
}
  
// This code is contributed by Chitranayal

Javascript

<script>
  
// JavaScript program for
// the above approach
  
// Function to find the minimum cost
// required to remove each character
// of the string in alphabetical order
function minSteps(str, N)
{
    var smaller,
    cost = 0;
      
    // Stores the frequency of
    // characters of the string
    var f = new Array(26).fill(0);
      
    // Iterate through the string
    for(var i = 0; i < N; i++) 
    {
        var curr_ele = str[i].charCodeAt(0) - 
                          "a".charCodeAt(0);
        smaller = 0;
          
        // Count the number of characters
        // smaller than the present character
        for(var j = 0; j <= curr_ele; j++) 
        {
            if (f[j] !== 0) 
                smaller += f[j];
        }
          
        // If no smaller character
        // precedes current character
        if (smaller === 0) 
            cost += i + 1;
        else 
            cost += i - smaller + 1;
          
        // Increase the frequency of
        // the current character
        f[str[i].charCodeAt(0) - 
             "a".charCodeAt(0)]++;
    }
      
    // Return the
    // total cost
    return cost;
}
  
// Driver Code
  
// Given string str
var str = "abcab";
var N = str.length;
  
// Function call
document.write(minSteps(str, N));
  
// This code is contributed by rdtank
  
</script>
Producción: 

8

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

Publicación traducida automáticamente

Artículo escrito por vatsalanarang 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 *