Dada la string str que consta solo de letras en minúsculas y un número entero K . La tarea es encontrar el costo mínimo para modificar la string de modo que la diferencia de valor ASCII entre dos caracteres cualesquiera de la string dada sea menor que K .
Las siguientes operaciones se pueden realizar en la string:
- Aumentar un carácter: por ejemplo, cuando aumenta ‘a’ en 1 , se convierte en ‘b’ . De manera similar, si aumenta ‘z’ en 1 , se convierte en ‘a’ . El incremento se realiza de forma cíclica.
- Disminución de un carácter: por ejemplo, cuando disminuye ‘a’ en 1 , se convierte en ‘z’ . De manera similar, si disminuye ‘z’ en 1 , se convierte en ‘y’ . La disminución se realiza de manera cíclica.
Ejemplos:
Entrada: str = “abcd”, K = 1
Salida: 2
Cambie ‘a’ por ‘b’ con costo 1 y ‘d’ por ‘c’ nuevamente con costo 1.
Costo total = 1 + 1 = 2.
La string modificada será «bbcc»Entrada: str = “abcdefghi”, K = 2
Salida: 12
Enfoque: la idea es mantener una tabla hash para todos los caracteres de la string para reducir la complejidad del tiempo en lugar de tomar un carácter a la vez. Necesitamos verificar todas las ventanas que contienen k caracteres contiguos y encontrar el costo mínimo entre todas las ventanas para modificar todos los caracteres de la string.
El costo de la modificación de un personaje se divide en las siguientes categorías:
- Caso 1: Si los personajes están dentro de la ventana, no incurrirá en ningún costo por modificarlos.
- Caso 2: si la ventana está entre los caracteres az y el carácter está en el lado izquierdo de la ventana.
- Si aumentamos el personaje que tendrá un costo de d1 o si disminuimos el personaje que tendrá un costo de d2+d3, encontramos un mínimo de d1 y d2+d3.
Si la ventana está entre los caracteres az y el carácter está en el lado derecho de la ventana.
- Si disminuimos el personaje que tendrá un costo de d1 o si aumentamos el personaje que tendrá un costo de d2+d3, encontramos un mínimo de d1 y d2+d3.
- Caso 3: Si la ventana es una subventana de caracteres que terminan en z y comienzan en a y si el carácter está fuera de la ventana.
- Si aumentamos el carácter incurrirá en un costo de d1 y si disminuimos el carácter incurrirá en un costo de d2, encontramos un mínimo entre d1 y d2.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the minimum cost
int minCost(string str, int K)
{
int n = str.length();
// Initialize result
int res = 999999999, count = 0, a, b;
// To store the frequency of characters
// of the string
int cnt[27];
// Initialize array with 0
memset(cnt, 0, sizeof(cnt));
// Update the frequencies of the
// characters of the string
for (int i = 0; i < n; i++)
cnt[str[i] - 'a' + 1]++;
// Loop to check all windows from a-z
// where window size is K
for (int i = 1; i < (26 - K + 1); i++) {
// Starting index of window
a = i;
// Ending index of window
b = i + K;
count = 0;
for (int j = 1; j <= 26; j++) {
// Check if the string contains character
if (cnt[j] > 0) {
// Check if the character is on left side of window
// find the cost of modification for character
// add value to count
// calculate nearest distance of modification
if (j >= a && j >= b)
count = count + (min(j - b, 25 - j + a + 1)) * cnt[j];
// Check if the character is on right side of window
// find the cost of modification for character
// add value to count
// calculate nearest distance of modification
else if (j <= a && j <= b)
count = count + (min(a - j, 25 + j - b + 1)) * cnt[j];
}
}
// Find the minimum of all costs
// for modifying the string
res = min(res, count);
}
// Loop to check all windows
// Here window contains characters
// before z and after z of window size K
for (int i = 26 - K + 1; i <= 26; i++) {
// Starting index of window
a = i;
// Ending index of window
b = (i + K) % 26;
count = 0;
for (int j = 1; j <= 26; j++) {
// Check if the string contains character
if (cnt[j] > 0) {
// If characters are outside window
// find the cost for modifying character
// add value to count
if (j >= b and j <= a)
count = count + (min(j - b, a - j)) * cnt[j];
}
}
// Find the minimum of all costs
// for modifying the string
res = min(res, count);
}
return res;
}
// Driver code
int main()
{
string str = "abcdefghi";
int K = 2;
cout << minCost(str, K);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.Arrays;
class GFG
{
// Function to return the minimum cost
static int minCost(String str, int K)
{
int n = str.length();
// Initialize result
int res = 999999999, count = 0, a, b;
// To store the frequency of characters
// of the string
int cnt[] = new int[27];
// Initialize array with 0
Arrays.fill(cnt, 0);
// Update the frequencies of the
// characters of the string
for (int i = 0; i < n; i++)
cnt[str.charAt(i) - 'a' + 1]++;
// Loop to check all windows from a-z
// where window size is K
for (int i = 1; i < (26 - K + 1); i++)
{
// Starting index of window
a = i;
// Ending index of window
b = i + K;
count = 0;
for (int j = 1; j <= 26; j++)
{
// Check if the string contains character
if (cnt[j] > 0)
{
// Check if the character is on left side of window
// find the cost of modification for character
// add value to count
// calculate nearest distance of modification
if (j >= a && j >= b)
count = count + (Math.min(j - b,
25 - j + a + 1)) * cnt[j];
// Check if the character is on right side of window
// find the cost of modification for character
// add value to count
// calculate nearest distance of modification
else if (j <= a && j <= b)
count = count + (Math.min(a - j,
25 + j - b + 1)) * cnt[j];
}
}
// Find the minimum of all costs
// for modifying the string
res = Math.min(res, count);
}
// Loop to check all windows
// Here window contains characters
// before z and after z of window size K
for (int i = 26 - K + 1; i <= 26; i++)
{
// Starting index of window
a = i;
// Ending index of window
b = (i + K) % 26;
count = 0;
for (int j = 1; j <= 26; j++)
{
// Check if the string contains character
if (cnt[j] > 0)
{
// If characters are outside window
// find the cost for modifying character
// add value to count
if (j >= b && j <= a)
count = count + (Math.min(j - b, a - j)) * cnt[j];
}
}
// Find the minimum of all costs
// for modifying the string
res = Math.min(res, count);
}
return res;
}
// Driver code
public static void main(String[] args)
{
String str = "abcdefghi";
int K = 2;
System.out.println(minCost(str, K));
}
}
/* This code contributed by PrinciRaj1992 */
Python3
# Python 3 implementation of the approach
# Function to return the minimum cost
def minCost(str1, K):
n = len(str1)
# Initialize result
res = 999999999
count = 0
# To store the frequency of characters
# of the string
cnt = [0 for i in range(27)]
# Update the frequencies of the
# characters of the string
for i in range(n):
cnt[ord(str1[i]) - ord('a') + 1] += 1
# Loop to check all windows from a-z
# where window size is K
for i in range(1, 26 - K + 1, 1):
# Starting index of window
a = i
# Ending index of window
b = i + K
count = 0
for j in range(1, 27, 1):
# Check if the string contains character
if (cnt[j] > 0):
# Check if the character is on left side of window
# find the cost of modification for character
# add value to count
# calculate nearest distance of modification
if (j >= a and j >= b):
count = count + (min(j - b, 25 -
j + a + 1)) * cnt[j]
# Check if the character is on right side of window
# find the cost of modification for character
# add value to count
# calculate nearest distance of modification
elif (j <= a and j <= b):
count = count + (min(a - j, 25 +
j - b + 1)) * cnt[j]
# Find the minimum of all costs
# for modifying the string
res = min(res, count)
# Loop to check all windows
# Here window contains characters
# before z and after z of window size K
for i in range(26 - K + 1, 27, 1):
# Starting index of window
a = i
# Ending index of window
b = (i + K) % 26
count = 0
for j in range(1, 27, 1):
# Check if the string contains character
if (cnt[j] > 0):
# If characters are outside window
# find the cost for modifying character
# add value to count
if (j >= b and j <= a):
count = count + (min(j - b,
a - j)) * cnt[j]
# Find the minimum of all costs
# for modifying the string
res = min(res, count)
return res
# Driver code
if __name__ == '__main__':
str1 = "abcdefghi"
K = 2
print(minCost(str1, K))
# This code is contributed by
# Surendra_Gangwar
C#
// C# program to implement
// the above approach
using System;
class GFG
{
// Function to return the minimum cost
static int minCost(String str, int K)
{
int n = str.Length;
// Initialize result
int res = 999999999, count = 0, a, b;
// To store the frequency of characters
// of the string
int []cnt = new int[27];
// Update the frequencies of the
// characters of the string
for (int i = 0; i < n; i++)
cnt[str[i] - 'a' + 1]++;
// Loop to check all windows from a-z
// where window size is K
for (int i = 1; i < (26 - K + 1); i++)
{
// Starting index of window
a = i;
// Ending index of window
b = i + K;
count = 0;
for (int j = 1; j <= 26; j++)
{
// Check if the string contains character
if (cnt[j] > 0)
{
// Check if the character is on left side of window
// find the cost of modification for character
// add value to count
// calculate nearest distance of modification
if (j >= a && j >= b)
count = count + (Math.Min(j - b,
25 - j + a + 1)) * cnt[j];
// Check if the character is on right side of window
// find the cost of modification for character
// add value to count
// calculate nearest distance of modification
else if (j <= a && j <= b)
count = count + (Math.Min(a - j,
25 + j - b + 1)) * cnt[j];
}
}
// Find the minimum of all costs
// for modifying the string
res = Math.Min(res, count);
}
// Loop to check all windows
// Here window contains characters
// before z and after z of window size K
for (int i = 26 - K + 1; i <= 26; i++)
{
// Starting index of window
a = i;
// Ending index of window
b = (i + K) % 26;
count = 0;
for (int j = 1; j <= 26; j++)
{
// Check if the string contains character
if (cnt[j] > 0)
{
// If characters are outside window
// find the cost for modifying character
// add value to count
if (j >= b && j <= a)
count = count + (Math.Min(j - b, a - j)) * cnt[j];
}
}
// Find the minimum of all costs
// for modifying the string
res = Math.Min(res, count);
}
return res;
}
// Driver code
public static void Main(String[] args)
{
String str = "abcdefghi";
int K = 2;
Console.WriteLine(minCost(str, K));
}
}
// This code has been contributed by 29AjayKumar
PHP
<?php
// PHP implementation of the approach
// Function to return the minimum cost
function minCost($str, $K)
{
$n = strlen($str);
// Initialize result
$res = 999999999; $count = 0;
// To store the frequency of characters
// of the string
// Initialize array with 0
$cnt = array_fill(0, 27, 0);
// Update the frequencies of the
// characters of the string
for ($i = 0; $i < $n; $i++)
$cnt[ord($str[$i]) - ord('a') + 1]++;
// Loop to check all windows from a-z
// where window size is K
for ($i = 1; $i < (26 - $K + 1); $i++)
{
// Starting index of window
$a = $i;
// Ending index of window
$b = $i + $K;
$count = 0;
for ($j = 1; $j <= 26; $j++)
{
// Check if the string contains character
if ($cnt[$j] > 0)
{
// Check if the character is on left side of window
// find the cost of modification for character
// add value to count
// calculate nearest distance of modification
if ($j >= $a && $j >= $b)
$count = $count + (min($j - $b, 25 - $j + $a + 1)) * $cnt[$j];
// Check if the character is on right side of window
// find the cost of modification for character
// add value to count
// calculate nearest distance of modification
else if ($j <= $a && $j <=$b)
$count = $count + (min($a - $j, 25 + $j - $b + 1)) * $cnt[$j];
}
}
// Find the minimum of all costs
// for modifying the string
$res = min($res, $count);
}
// Loop to check all windows
// Here window contains characters
// before z and after z of window size K
for ($i = 26 - $K + 1; $i <= 26; $i++)
{
// Starting index of window
$a = $i;
// Ending index of window
$b = ($i + $K) % 26;
$count = 0;
for ($j = 1; $j <= 26; $j++)
{
// Check if the string contains character
if ($cnt[$j] > 0)
{
// If characters are outside window
// find the cost for modifying character
// add value to count
if ($j >= $b and $j <= $a)
$count = $count + (min($j - $b,$a - $j)) * $cnt[$j];
}
}
// Find the minimum of all costs
// for modifying the string
$res = min($res, $count);
}
return $res;
}
// Driver code
$str = "abcdefghi";
$K = 2;
echo minCost($str, $K);
// This code is contributed by Ryuga
?>
Javascript
<script>
// Javascript implementation of the approach
// Function to return the minimum cost
function minCost(str, K)
{
var n = str.length;
// Initialize result
var res = 999999999, count = 0, a, b;
// To store the frequency of characters
// of the string
var cnt = Array(27).fill(0);
// Update the frequencies of the
// characters of the string
for (var i = 0; i < n; i++)
cnt[str[i].charCodeAt(0) - 97 + 1]++;
// Loop to check all windows from a-z
// where window size is K
for (var i = 1; i < (26 - K + 1); i++) {
// Starting index of window
a = i;
// Ending index of window
b = i + K;
count = 0;
for (var j = 1; j <= 26; j++) {
// Check if the string contains character
if (cnt[j] > 0) {
// Check if the character is on left side of window
// find the cost of modification for character
// add value to count
// calculate nearest distance of modification
if (j >= a && j >= b)
count = count + (Math.min(j - b, 25 - j + a + 1)) * cnt[j];
// Check if the character is on right side of window
// find the cost of modification for character
// add value to count
// calculate nearest distance of modification
else if (j <= a && j <= b)
count = count + (Math.min(a - j, 25 + j - b + 1)) * cnt[j];
}
}
// Find the minimum of all costs
// for modifying the string
res = Math.min(res, count);
}
// Loop to check all windows
// Here window contains characters
// before z and after z of window size K
for (var i = 26 - K + 1; i <= 26; i++) {
// Starting index of window
a = i;
// Ending index of window
b = (i + K) % 26;
count = 0;
for (var j = 1; j <= 26; j++) {
// Check if the string contains character
if (cnt[j] > 0) {
// If characters are outside window
// find the cost for modifying character
// add value to count
if (j >= b && j <= a)
count = count + (Math.min(j - b, a - j)) * cnt[j];
}
}
// Find the minimum of all costs
// for modifying the string
res = Math.min(res, count);
}
return res;
}
// Driver code
var str = "abcdefghi";
var K = 2;
document.write( minCost(str, K));
</script>
Producción:
12
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por Sairahul Jella y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA