Dada una string S que consta de N alfabetos ingleses en minúsculas, un número entero K y una array cost[] de tamaño 26 que denota el costo de cada alfabeto inglés en minúsculas, la tarea es encontrar el costo mínimo para construir una subsecuencia de longitud K a partir de los caracteres de la string S .
Ejemplos:
Entrada: S = “aabcbc”, K = 3, costo[] = {2, 1, 3, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9 , 9, 9, 9, 9, 9, 9, 9, 9, 9}
Salida: 4
Explicación:
Una manera de construir una string de tamaño K(= 3) es:
Forme la string “abb” tomando dos ‘b’ con un costo de (2*1 = 2), y una ‘a’ con un costo de (1*2 = 2).
Por lo tanto, el costo total para construir la string “abb” es (2 + 2 = 4), que es el mínimo posible.Entrada: S = “aaaca”, K = 1, costo[] = {2, 1, 3, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9 , 9, 9, 9, 9, 9, 9, 9, 9, 9}
Salida: 2
Enfoque : el problema dado se puede resolver ordenando el costo de la array [] en orden creciente e incluir los primeros K caracteres que tienen el costo mínimo que están presentes en la string S dada . Siga los pasos a continuación para resolver el problema:
- Inicialice un vector de par de caracteres e int, digamos, V para almacenar el carácter y el costo de ese carácter.
- Además, inicialice un mapa , digamos mp con clave como carácter y valor como números enteros para almacenar la frecuencia de cada carácter de la string S .
- Recorra la string dada usando la variable i y en cada iteración incremente el valor de mp[S[i]] .
- Iterar sobre el rango [0, 25] usando la variable i y en cada iteración agregar el par {char(‘a’ + i), cost[i]} al vector de pares V .
- Ordene el vector de pares V[]según el segundo elemento del par .
- Ahora, inicialice una variable, digamos minCost como 0 para almacenar el costo mínimo de una subsecuencia de longitud K .
- Iterar sobre el rango [0, 25] usando la variable i y realizar los siguientes pasos:
- Inicialice una variable, por ejemplo, cuente como mp[‘a’ + i] .
- Si el valor de count es menor que K , agregue el valor de count*V[i].second al valor de minCost y actualice el valor de K a K – count .
- De lo contrario, agregue K*V[i].segundo al valor de minCost y salga del bucle .
- Después de completar los pasos anteriores, imprima el valor de minCost como resultado.
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;
// Custom comparator to sort according
// to the second element
bool comparator(pair<char, int> p1,
pair<char, int> p2)
{
return p1.second < p2.second;
}
// Function to find the minimum cost
// to construct a subsequence of the
// length K
int minimumCost(string S, int N,
int K, int cost[])
{
// Stores the minimum cost
int minCost = 0;
// Stores the pair of character
// and the cost of that character
vector<pair<char, int> > V;
// Stores the frequency of each
// character
unordered_map<char, int> mp;
// Iterate in the range [0, N-1]
for (int i = 0; i < N; i++)
mp[S[i]]++;
// Iterate in the range [0, 25]
for (int i = 0; i < 26; i++) {
V.push_back({ char('a' + i), cost[i] });
}
// Sort the vector of pairs V
// wrt the second element
sort(V.begin(), V.end(), comparator);
// Iterate in the range [0, 25]
for (int i = 0; i < 26; i++) {
// Stores the frequency of the
// current char in the string
int count = mp[char('a' + i)];
// If count is less than
// or equal to K
if (count >= K) {
// Update the value of
// minCost
minCost += V[i].second * K;
break;
}
else if (count < K) {
// Update the value of
// minCost
minCost += V[i].second * count;
// Update the value
// of K
K = K - count;
}
}
// Print the value of minCost
return minCost;
}
// Driver Code
int main()
{
string S = "aabcbc";
int K = 3;
int cost[26] = { 2, 1, 3, 9, 9, 9, 9,
9, 9, 9, 9, 9, 9, 9,
9, 9, 9, 9, 9, 9, 9,
9, 9, 9, 9, 9 };
int N = S.length();
cout << minimumCost(S, N, K, cost);
return 0;
}
Python3
# Python3 program for the above approach
# Function to find the minimum cost
# to construct a subsequence of the
# length K
def minimumCost(S, N, K, cost):
# Stores the minimum cost
minCost = 0
# Stores the pair of character
# and the cost of that character
V = []
# Stores the frequency of each
# character
mp = {}
# Iterate in the range [0, N-1]
for i in range(N):
if (S[i] in mp):
mp[S[i]] += 1
else:
mp[S[i]] = 1
# Iterate in the range [0, 25]
for i in range(26):
V.append([chr(ord('a') + i), cost[i]])
# Sort the array of pairs V
# with the second element
while (1):
flag = 0
for i in range(len(V) - 1):
if (V[i][1] > V[i + 1][1]):
temp = V[i]
V[i] = V[i + 1]
V[i + 1] = temp
flag = 1
if (flag == 0):
break
# Iterate in the range [0, 25]
for i in range(26):
# Stores the frequency of the
# current char in the string
count = mp[chr(ord('a') + i)]
# If count is less than
# or equal to K
if (count >= K):
# Update the value of
# minCost
minCost += V[i][1] * K
break
elif (count < K):
# Update the value of
# minCost
minCost += V[i][1] * count
# Update the value
# of K
K = K - count
# Print the value of minCost
return minCost
# Driver Code
S = "aabcbc"
K = 3
cost = [ 2, 1, 3, 9, 9, 9, 9,
9, 9, 9, 9, 9, 9, 9,
9, 9, 9, 9, 9, 9, 9,
9, 9, 9, 9, 9 ]
N = len(S)
print(minimumCost(S, N, K, cost))
# This code is contributed by _saurabh_jaiswal
Javascript
<script>
// Javascript program for the above approach
// Function to find the minimum cost
// to construct a subsequence of the
// length K
function minimumCost(S, N, K, cost) {
// Stores the minimum cost
let minCost = 0;
// Stores the pair of character
// and the cost of that character
let V = [];
// Stores the frequency of each
// character
let mp = new Map();
// Iterate in the range [0, N-1]
for (let i = 0; i < N; i++) {
if (mp.has(S[i])) {
mp.set(S[i], mp.get(S[i]) + 1)
} else {
mp.set(S[i], 1)
}
}
// Iterate in the range [0, 25]
for (let i = 0; i < 26; i++) {
V.push([String.fromCharCode('a'.charCodeAt(0) + i), cost[i]]);
}
// Sort the array of pairs V
// with the second element
while (1) {
let flag = 0;
for (let i = 0; i < V.length - 1; i++) {
if (V[i][1] > V[i + 1][1]) {
let temp = V[i];
V[i] = V[i + 1];
V[i + 1] = temp;
flag = 1
}
}
if(flag == 0){
break
}
}
// Iterate in the range [0, 25]
for (let i = 0; i < 26; i++) {
// Stores the frequency of the
// current char in the string
let count = mp.get(String.fromCharCode('a'.charCodeAt(0) + i));
// If count is less than
// or equal to K
if (count >= K) {
// Update the value of
// minCost
minCost += V[i][1] * K;
break;
}
else if (count < K) {
// Update the value of
// minCost
minCost += V[i][1] * count;
// Update the value
// of K
K = K - count;
}
}
// Print the value of minCost
return minCost;
}
// Driver Code
let S = "aabcbc";
let K = 3;
let cost = [2, 1, 3, 9, 9, 9, 9,
9, 9, 9, 9, 9, 9, 9,
9, 9, 9, 9, 9, 9, 9,
9, 9, 9, 9, 9];
let N = S.length;
document.write(minimumCost(S, N, K, cost));
// This code is contributed by gfgking.
</script>
Producción:
4
Complejidad temporal: O(N)
Espacio auxiliar: O(1)