Dada una string str que consta de caracteres y espacios, la tarea es encontrar el costo mínimo para reducir la cantidad de espacios entre los caracteres de la string.
El costo de mover un carácter para el índice i al índice j se define como: | yo – j |
Ejemplos:
Entrada: str = ” @ $”
Salida: 4
Explicación:
Como los caracteres están en los índices [2, 7] (solo dos), mueva el primer carácter al segundo carácter más cercano o viceversa. El costo requerido es |2-6| = 4 o |6-2| = 4.
Por lo tanto, el costo mínimo es 4.Entrada: str = ” A ”
Salida: 0
Explicación:
Dado que la string consta de un solo carácter, no se requieren cambios. Por lo tanto, el costo mínimo es 0.
Enfoque: la idea es mover todos los caracteres lo más cerca posible de la mitad de la string para minimizar el costo total. A continuación se muestran los pasos:
- Inicializar el costo total con 0.
- Transverse la string y cuente los espacios entre los dos caracteres.
- Reúna a ambos personajes y agregue el costo al costo total.
- Repita los pasos anteriores para todos los personajes.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to gather characters
// of a string in minimum cost
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the
// minimum cost
int min_cost(string S)
{
// Stores the minimum cost
int cost = 0;
// Stores the count of
// characters found
int F = 0;
// Stores the count of
// blank spaces found
int B = 0;
int count = 0;
for(char c : S)
if(c == ' ')
count++;
// Stores the count of
// total characters
int n = S.size() - count;
// If the count of characters
// is equal to 1
if (n == 1)
return cost;
// Iterate over the string
for(char in : S)
{
// Consider the previous character
// together with current character
if (in != ' ')
{
// If not together already
if (B != 0)
{
// Add the cost to group
// them together
cost += min(n - F, F) * B;
B = 0;
}
// Increase count of
// characters found
F += 1;
}
// Otherwise
else
{
// Increase count of
// spaces found
B += 1;
}
}
// Return the total
// cost obtained
return cost;
}
// Driver Code
int main ()
{
string S = " @ $";
cout << min_cost(S);
return 0;
}
// This code is contributed by Amit Katiyar
Java
// Java program to gather characters
// of a string in minimum cost
import java.util.*;
import java.lang.*;
class GFG{
// Function to calculate the
// minimum cost
static int min_cost(String S)
{
// Stores the minimum cost
int cost = 0;
// Stores the count of
// characters found
int F = 0;
// Stores the count of
// blank spaces found
int B = 0;
int count = 0;
for(char c : S.toCharArray())
if(c == ' ')
count++;
// Stores the count of
// total characters
int n = S.length() - count;
// If the count of characters
// is equal to 1
if (n == 1)
return cost;
// Iterate over the string
for(char in : S.toCharArray())
{
// Consider the previous character
// together with current character
if (in != ' ')
{
// If not together already
if (B != 0)
{
// Add the cost to group
// them together
cost += Math.min(n - F, F) * B;
B = 0;
}
// Increase count of
// characters found
F += 1;
}
// Otherwise
else
{
// Increase count of
// spaces found
B += 1;
}
}
// Return the total
// cost obtained
return cost;
}
// Driver Code
public static void main (String[] args)
{
String S = " @ $";
System.out.println(min_cost(S));
}
}
// This code is contributed by offbeat
Python3
# Python3 program to gather characters
# of a string in minimum cost
# Function to calculate the
# minimum cost
def min_cost(S):
# Stores the minimum cost
cost = 0
# Stores the count of
# characters found
F = 0
# Stores the count of
# blank spaces found
B = 0
# Stores the count of
# total characters
n = len(S)-S.count(' ')
# If the count of characters
# is equal to 1
if n == 1:
return cost
# Iterate over the string
for char in S:
# Consider the previous character
# together with current character
if char != ' ':
# If not together already
if B != 0:
# Add the cost to group
# them together
cost += min(n - F, F) * B
B = 0
# Increase count of
# characters found
F += 1
# Otherwise
else:
# Increase count of
# spaces found
B += 1
# Return the total
# cost obtained
return cost
# Driver Code
S = " @ $"
print(min_cost(S))
C#
// C# program to gather characters
// of a string in minimum cost
using System;
class GFG{
// Function to calculate the
// minimum cost
static int min_cost(String S)
{
// Stores the minimum cost
int cost = 0;
// Stores the count of
// characters found
int F = 0;
// Stores the count of
// blank spaces found
int B = 0;
int count = 0;
foreach(char c in S.ToCharArray())
if(c == ' ')
count++;
// Stores the count of
// total characters
int n = S.Length - count;
// If the count of characters
// is equal to 1
if (n == 1)
return cost;
// Iterate over the string
foreach(char inn in S.ToCharArray())
{
// Consider the previous character
// together with current character
if (inn != ' ')
{
// If not together already
if (B != 0)
{
// Add the cost to group
// them together
cost += Math.Min(n - F, F) * B;
B = 0;
}
// Increase count of
// characters found
F += 1;
}
// Otherwise
else
{
// Increase count of
// spaces found
B += 1;
}
}
// Return the total
// cost obtained
return cost;
}
// Driver Code
public static void Main(String[] args)
{
String S = " @ $";
Console.WriteLine(min_cost(S));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to gather characters
// of a string in minimum cost
// Function to calculate the
// minimum cost
function min_cost(S)
{
// Stores the minimum cost
let cost = 0;
// Stores the count of
// characters found
let F = 0;
// Stores the count of
// blank spaces found
let B = 0;
let count = 0;
for(let i in S)
if(S[i] == ' ')
count++;
// Stores the count of
// total characters
let n = S.length - count;
// If the count of characters
// is equal to 1
if (n == 1)
return cost;
// Iterate over the string
for(let i in S)
{
// Consider the previous character
// together with current character
if (S[i] != ' ')
{
// If not together already
if (B != 0)
{
// Add the cost to group
// them together
cost += Math.min(n - F, F) * B;
B = 0;
}
// Increase count of
// characters found
F += 1;
}
// Otherwise
else
{
// Increase count of
// spaces found
B += 1;
}
}
// Return the total
// cost obtained
return cost;
}
// Driver Code
let S = " @ $";
document.write(min_cost(S.split('')));
</script>
Producción:
4
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por deepanshu_rustagi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA