Dada una string str y una array cost[] de tamaño N donde cost[i] denota el costo de eliminar el i -ésimo carácter de la string str , la tarea es encontrar el costo mínimo de las eliminaciones requeridas para hacer que cada carácter de la string único _
Ejemplos:
Entrada: str = “AAABBB”, costo = {1, 2, 3, 4, 5, 6}
Salida: 12
Explicación: Eliminar caracteres en los índices 0, 1, 3, 4 modifica str a “AB”. Por tanto, el coste total de las mudanzas = 1 + 2 + 4 + 5 = 12Entrada: str = “geeksforgeeks”, costo = {1, 2, 3, 4, 5, 5, 4, 3, 2, 1, 1, 2, 3}
Salida: 10
Explicación: Eliminar caracteres en los índices 0, 1, 9, 10, 11, 12 modifica str a «eksforg». Por tanto, el coste total de las mudanzas = 1 + 2 + 1 + 1 + 2 + 3 = 10
Enfoque ingenuo: el enfoque más simple para resolver el problema es recorrer la string y, para cada carácter, recorrer los caracteres restantes y encontrar sus ocurrencias. Almacene el costo máximo de eliminar una ocurrencia. Agregue el costo de eliminar todas las demás ocurrencias del personaje a la suma. Finalmente, después de completar esto para todos los caracteres de la string, imprima la suma final obtenida.
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 minimum cost of
// removing characters to make the String unique
int delCost(string s, int cost[], int l1, int l2)
{
// stores the visited character
bool visited[l1];
memset(visited, 0, sizeof(visited));
// stores the answer
int ans = 0;
// traverse the String
for (int i = 0; i < l1; i++)
{
// if already visited
if (visited[i])
{
continue;
}
// Stores the maximum cost of
// removing a particular character
int maxDel = 0;
// Store the total deletion cost of
// a particular character
int totalCost = 0;
// Mark the current character visited
visited[i] = 1;
// Traverse the indices of the String [i, N-1]
for (int j = i; j < l1; j++)
{
// If any duplicate is found
if (s[i] == s[j])
{
// Update the maximum cost
// and total cost
maxDel = max(maxDel, cost[j]);
totalCost += cost[j];
// Mark the current character visited
visited[j] = 1;
}
}
// Keep the character with
// maximum cost and delete the rest
ans += totalCost - maxDel;
}
// return the minimum cost
return ans;
}
// Driver code
int main()
{
// input String
string s = "AAABBB";
int l1 = s.size();
// input array
int cost[] = { 1, 2, 3, 4, 5, 6 };
int l2 = sizeof(cost) / sizeof(cost[0]);
// function call
cout << delCost(s, cost, l1, l2);
return 0;
}
// This code is contributed by gauravrajput1
Java
// Java program to implement
// the above approach
import java.io.*;
class GFG
{
// Function to find the minimum cost of
// removing characters to make the string unique
public static int delCost(String s, int[] cost)
{
// stores the visited character
boolean visited[] = new boolean[s.length()];
// stores the answer
int ans = 0;
// traverse the string
for (int i = 0; i < s.length(); i++)
{
// if already visited
if (visited[i])
{
continue;
}
// Stores the maximum cost of
// removing a particular character
int maxDel = 0;
// Store the total deletion cost of
// a particular character
int totalCost = 0;
// Mark the current character visited
visited[i] = true;
// Traverse the indices of the string [i, N-1]
for (int j = i; j < s.length(); j++)
{
// If any duplicate is found
if (s.charAt(i) == s.charAt(j))
{
// Update the maximum cost
// and total cost
maxDel = Math.max(maxDel, cost[j]);
totalCost += cost[j];
// Mark the current character visited
visited[j] = true;
}
}
// Keep the character with
// maximum cost and delete the rest
ans += totalCost - maxDel;
}
// return the minimum cost
return ans;
}
// Driver code
public static void main(String[] args)
{
// input string
String s = "AAABBB";
// input array
int[] cost = { 1, 2, 3, 4, 5, 6 };
// function call
System.out.println(delCost(s, cost));
}
}
// This code is contributed by aditya7409
Python3
# Python3 program to implement # the above approach # Function to find the minimum cost of # removing characters to make the string unique def delCost(s, cost): # Stores the visited characters visited = [False]*len(s) # Stores the answer ans = 0 # Traverse the string for i in range(len(s)): # If already visited if visited[i]: continue # Stores the maximum cost of # removing a particular character maxDel = 0 # Store the total deletion cost of # a particular character totCost = 0 # Mark the current character visited visited[i] = True # Traverse the indices of the string [i, N-1] for j in range(i, len(s)): # If any duplicate is found if s[i] == s[j]: # Update the maximum cost # and total cost maxDel = max(maxDel, cost[j]) totCost += cost[j] # Mark the current character visited visited[j] = True # Keep the character with # maximum cost and delete the rest ans += totCost - maxDel # Return the minimum cost return ans # Driver code # Given string string = "AAABBB" # Given cost array cost = [1, 2, 3, 4, 5, 6] # Function Call print(delCost(string, cost))
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the minimum cost of
// removing characters to make the string unique
public static int delCost(string s, int[] cost)
{
// Stores the visited character
bool[] visited = new bool[s.Length];
// Stores the answer
int ans = 0;
// Traverse the string
for(int i = 0; i < s.Length; i++)
{
// If already visited
if (visited[i] != false)
{
continue;
}
// Stores the maximum cost of
// removing a particular character
int maxDel = 0;
// Store the total deletion cost of
// a particular character
int totalCost = 0;
// Mark the current character visited
visited[i] = true;
// Traverse the indices of the
// string [i, N-1]
for(int j = i; j < s.Length; j++)
{
// If any duplicate is found
if (s[i] == s[j])
{
// Update the maximum cost
// and total cost
maxDel = Math.Max(maxDel, cost[j]);
totalCost += cost[j];
// Mark the current character visited
visited[j] = true;
}
}
// Keep the character with
// maximum cost and delete
// the rest
ans += totalCost - maxDel;
}
// Return the minimum cost
return ans;
}
// Driver Code
public static void Main ()
{
// Input string
string s = "AAABBB";
// Input array
int[] cost = { 1, 2, 3, 4, 5, 6 };
// Function call
Console.Write(delCost(s, cost));
}
}
// This code is contributed by code_hunt
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to find the minimum cost of
// removing characters to make the string unique
function delCost( s, cost) {
// stores the visited character
var visited =Array(s.length).fill(false);
// stores the answer
var ans = 0;
// traverse the string
for (i = 0; i < s.length; i++) {
// if already visited
if (visited[i]) {
continue;
}
// Stores the maximum cost of
// removing a particular character
var maxDel = 0;
// Store the total deletion cost of
// a particular character
var totalCost = 0;
// Mark the current character visited
visited[i] = true;
// Traverse the indices of the string [i, N-1]
for (j = i; j < s.length; j++) {
// If any duplicate is found
if (s.charAt(i) == s.charAt(j)) {
// Update the maximum cost
// and total cost
maxDel = Math.max(maxDel, cost[j]);
totalCost += cost[j];
// Mark the current character visited
visited[j] = true;
}
}
// Keep the character with
// maximum cost and delete the rest
ans += totalCost - maxDel;
}
// return the minimum cost
return ans;
}
// Driver code
// input string
var s = "AAABBB";
// input array
var cost = [ 1, 2, 3, 4, 5, 6 ];
// function call
document.write(delCost(s, cost));
// This code contributed by umadevi9616
</script>
Producción:
12
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es usar Hashmap . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos ans , para almacenar el costo mínimo requerido.
- Inicialice dos Hashmaps , digamos forMax y forTot , para almacenar el costo de eliminación máximo y total de cada personaje respectivamente.
- Recorre la string S usando la variable i .
- Actualice forMax[s[i]] = max(forMax(s[i]), cost[i]) .
- Actualizar forTot[s[i]] += cost[i] .
- Recorra el Hashmap para Max
- Para cada carácter, mantenga el carácter de costo máximo y elimine sus otros duplicados actualizando ans += forTot[i]-forMax[i] .
- Imprimir respuesta _
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum cost of
// removing characters to make the string unique
int delCost(string s, int cost[])
{
// Store the minimum cost required
int ans = 0;
// Create a dictionary to store the
// maximum cost of removal a character
map<char, int> forMax;
// Create a dictionary to store the total
// deletion cost of a character
map<char, int> forTot;
// Traverse the string, S
for (int i = 0; i < s.length(); i++) {
// Keep track of maximum cost of each character
if (!forMax[s[i]]) {
forMax[s[i]] = cost[i];
}
else {
// Update the maximum deletion cost
forMax[s[i]] = max(cost[i], forMax[s[i]]);
}
// Keep track of the total cost of each character
if (!forTot[s[i]]) {
forTot[s[i]] = cost[i];
}
else {
// Update the total deletion cost
forTot[s[i]] = forTot[s[i]] + cost[i];
}
}
// Traverse through all the unique characters
for (auto i : forMax) {
// Keep the maximum cost character and
// delete the rest
ans += forTot[i.first] - i.second;
}
// Return the answer
return ans;
}
// Driver code
int main()
{
// Given string
string s = "AAABBB";
// Given cost array
int cost[] = { 1, 2, 3, 4, 5, 6 };
// Function Call
cout << (delCost(s, cost));
}
// This code is contributed by ukasp.
Java
// Java program for the above approach
import java.util.*;
public class GFG
{
// Function to find the minimum cost of
// removing characters to make the string unique
static int delCost(String s, int[] cost)
{
// Store the minimum cost required
int ans = 0;
// Create a dictionary to store the
// maximum cost of removal a character
HashMap<Character, Integer> forMax = new HashMap<>();
// Create a dictionary to store the total
// deletion cost of a character
HashMap<Character, Integer> forTot = new HashMap<>();
// Traverse the string, S
for(int i = 0; i < s.length(); i++)
{
// Keep track of maximum cost of each character
if(!forMax.containsKey(s.charAt(i)))
{
forMax.put(s.charAt(i), cost[i]);
}
else
{
// Update the maximum deletion cost
forMax.put(s.charAt(i), Math.max(cost[i], forMax.get(s.charAt(i))));
}
// Keep track of the total cost of each character
if(!forTot.containsKey(s.charAt(i)))
{
forTot.put(s.charAt(i), cost[i]);
}
else
{
// Update the total deletion cost
forTot.put(s.charAt(i), forTot.get(s.charAt(i)) + cost[i]);
}
}
// Traverse through all the unique characters
for (Map.Entry<Character, Integer> i : forMax.entrySet())
{
// Keep the maximum cost character and
// delete the rest
ans += forTot.get(i.getKey()) - i.getValue();
}
// Return the answer
return ans;
}
// Driver code
public static void main(String[] args)
{
// Given string
String s = "AAABBB";
// Given cost array
int[] cost = {1, 2, 3, 4, 5, 6};
// Function Call
System.out.println(delCost(s, cost));
}
}
// This code is contributed by divyeshrabaddiya07.
Python3
# Python3 program to implement
# the above approach
# Function to find the minimum cost of
# removing characters to make the string unique
def delCost(s, cost):
# Store the minimum cost required
ans = 0
# Create a dictionary to store the
# maximum cost of removal a character
forMax = {}
# Create a dictionary to store the total
# deletion cost of a character
forTot = {}
# Traverse the string, S
for i in range(len(s)):
# Keep track of maximum cost of each character
if s[i] not in forMax:
forMax[s[i]] = cost[i]
else:
# Update the maximum deletion cost
forMax[s[i]] = max(cost[i], forMax[s[i]])
# Keep track of the total cost of each character
if s[i] not in forTot:
forTot[s[i]] = cost[i]
else:
# Update the total deletion cost
forTot[s[i]] += cost[i]
# Traverse through all the unique characters
for i in forMax:
# Keep the maximum cost character and
# delete the rest
ans += forTot[i] - forMax[i]
# Return the answer
return ans
# Driver code
# Given string
string = "AAABBB"
# Given cost array
cost = [1, 2, 3, 4, 5, 6]
# Function Call
print(delCost(string, cost))
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to find the minimum cost of
// removing characters to make the string unique
static int delCost(string s, int[] cost)
{
// Store the minimum cost required
int ans = 0;
// Create a dictionary to store the
// maximum cost of removal a character
Dictionary<int, int> forMax = new Dictionary<int, int>();
// Create a dictionary to store the total
// deletion cost of a character
Dictionary<int, int> forTot = new Dictionary<int, int>();
// Traverse the string, S
for(int i = 0; i < s.Length; i++)
{
// Keep track of maximum cost of each character
if(!forMax.ContainsKey(s[i]))
{
forMax[s[i]] = cost[i];
}
else
{
// Update the maximum deletion cost
forMax[s[i]] = Math.Max(cost[i], forMax[s[i]]);
}
// Keep track of the total cost of each character
if(!forTot.ContainsKey(s[i]))
{
forTot[s[i]] = cost[i];
}
else
{
// Update the total deletion cost
forTot[s[i]] += cost[i];
}
}
// Traverse through all the unique characters
foreach(KeyValuePair<int, int> i in forMax)
{
// Keep the maximum cost character and
// delete the rest
ans += forTot[i.Key] - i.Value;
}
// Return the answer
return ans;
}
// Driver code
static void Main()
{
// Given string
string s = "AAABBB";
// Given cost array
int[] cost = {1, 2, 3, 4, 5, 6};
// Function Call
Console.WriteLine(delCost(s, cost));
}
}
// This code is contributed by divyesh072019
Javascript
<script>
// JavaScript program for the above approach
// Function to find the minimum cost of
// removing characters to make the string unique
function delCost(s, cost)
{
// Store the minimum cost required
var ans = 0;
// Create a dictionary to store the
// maximum cost of removal a character
var forMax = new Map();
// Create a dictionary to store the total
// deletion cost of a character
var forTot = new Map();
// Traverse the string, S
for (var i = 0; i < s.length; i++) {
// Keep track of maximum cost of each character
if (!forMax.has(s[i])) {
forMax.set(s[i], cost[i]);
}
else {
// Update the maximum deletion cost
forMax.set(s[i], Math.max(forMax.get(s[i]),cost[i]))
}
// Keep track of the total cost of each character
if (!forTot.has(s[i])) {
forTot.set(s[i], cost[i]);
}
else {
// Update the total deletion cost
forTot.set(s[i], forTot.get(s[i]) + cost[i])
}
}
// Traverse through all the unique characters
forMax.forEach((value, key) => {
// Keep the maximum cost character and
// delete the rest
ans += forTot.get(key) - value;
});
// Return the answer
return ans;
}
// Driver code
// Given string
var s = "AAABBB";
// Given cost array
var cost = [1, 2, 3, 4, 5, 6];
// Function Call
document.write(delCost(s, cost));
</script>
Producción:
12
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por rohitsingh07052 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA