Dada una string str de caracteres en minúsculas, la tarea es encontrar la cantidad mínima de caracteres que deben agregarse a la string para equilibrarla. Se dice que una string está balanceada si y solo si el número de ocurrencias de cada uno de los caracteres es igual.
Ejemplos:
Entrada: str = “geeksforgeeks”
Salida: 15
Agregue 2 ‘g’, 2 ’k’, 2 ‘s’, 3 ‘f’, 3 ‘o’ y 3 ‘r’.
Entrada: str = “abcd”
Salida: 0
La string ya está balanceada.
Enfoque: Para minimizar las adiciones requeridas, la frecuencia de cada carácter debe ser igual a la frecuencia del elemento que ocurre con mayor frecuencia. Primero, cree una array de frecuencia y encuentre la frecuencia de todos los caracteres de la string dada. Ahora, la respuesta requerida será la suma de las diferencias absolutas de la frecuencia de cada carácter con la frecuencia máxima de la array de frecuencias.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define MAX 26
// Function to return the minimum additions
// required to balance the given string
int minimumAddition(string str, int len)
{
// To store the frequency of
// the characters of str
int freq[MAX] = { 0 };
// Update the frequency of the characters
for (int i = 0; i < len; i++) {
freq[str[i] - 'a']++;
}
// To store the maximum frequency from the array
int maxFreq = *max_element(freq, freq + MAX);
// To store the minimum additions required
int minAddition = 0;
for (int i = 0; i < MAX; i++) {
// Every character's frequency must be
// equal to the frequency of the most
// frequently occurring character
if (freq[i] > 0) {
minAddition += abs(maxFreq - freq[i]);
}
}
return minAddition;
}
// Driver code
int main()
{
string str = "geeksforgeeks";
int len = str.length();
cout << minimumAddition(str, len);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
final static int MAX = 26;
static int max_element(int freq[])
{
int max_ele = freq[0];
for(int i = 0; i < MAX; i++)
{
if(max_ele < freq[i])
max_ele = freq[i];
}
return max_ele;
}
// Function to return the minimum additions
// required to balance the given string
static int minimumAddition(String str, int len)
{
// To store the frequency of
// the characters of str
int freq[] = new int[MAX];
// Update the frequency of the characters
for (int i = 0; i < len; i++)
{
freq[str.charAt(i) - 'a']++;
}
// To store the maximum frequency from the array
int maxFreq = max_element(freq);
// To store the minimum additions required
int minAddition = 0;
for (int i = 0; i < MAX; i++)
{
// Every character's frequency must be
// equal to the frequency of the most
// frequently occurring character
if (freq[i] > 0)
{
minAddition += Math.abs(maxFreq - freq[i]);
}
}
return minAddition;
}
// Driver code
public static void main (String[] args)
{
String str = "geeksforgeeks";
int len = str.length();
System.out.println(minimumAddition(str, len));
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 implementation of the approach
MAX = 26
# Function to return the minimum additions
# required to balance the given string
def minimumAddition(str1, Len):
# To store the frequency of
# the characters of str1
freq = [0 for i in range(MAX)]
# Update the frequency of the characters
for i in range(Len):
freq[ord(str1[i]) - ord('a')] += 1
# To store the maximum frequency from the array
maxFreq = max(freq)
# To store the minimum additions required
minAddition = 0
for i in range(MAX):
# Every character's frequency must be
# equal to the frequency of the most
# frequently occurring character
if (freq[i] > 0):
minAddition += abs(maxFreq - freq[i])
return minAddition
# Driver code
str1 = "geeksforgeeks"
Len = len(str1)
print(minimumAddition(str1, Len))
# This code is contributed Mohit Kumar
C#
// C# implementation of the approach
using System;
class GFG
{
static int MAX = 26;
static int max_element(int []freq)
{
int max_ele = freq[0];
for(int i = 0; i < MAX; i++)
{
if(max_ele < freq[i])
max_ele = freq[i];
}
return max_ele;
}
// Function to return the minimum additions
// required to balance the given string
static int minimumAddition(String str, int len)
{
// To store the frequency of
// the characters of str
int []freq = new int[MAX];
// Update the frequency of the characters
for (int i = 0; i < len; i++)
{
freq[str[i] - 'a']++;
}
// To store the maximum frequency from the array
int maxFreq = max_element(freq);
// To store the minimum additions required
int minAddition = 0;
for (int i = 0; i < MAX; i++)
{
// Every character's frequency must be
// equal to the frequency of the most
// frequently occurring character
if (freq[i] > 0)
{
minAddition += Math.Abs(maxFreq - freq[i]);
}
}
return minAddition;
}
// Driver code
public static void Main (String[] args)
{
String str = "geeksforgeeks";
int len = str.Length;
Console.WriteLine(minimumAddition(str, len));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of the approach
let MAX = 26;
function max_element(freq)
{
let max_ele = freq[0];
for(let i = 0; i < MAX; i++)
{
if(max_ele < freq[i])
max_ele = freq[i];
}
return max_ele;
}
// Function to return the minimum additions
// required to balance the given string
function minimumAddition(str, len)
{
// To store the frequency of
// the characters of str
let freq = new Array(MAX);
freq.fill(0);
// Update the frequency of the characters
for (let i = 0; i < len; i++)
{
freq[str[i].charCodeAt() - 'a'.charCodeAt()]++;
}
// To store the maximum frequency from the array
let maxFreq = max_element(freq);
// To store the minimum additions required
let minAddition = 0;
for (let i = 0; i < MAX; i++)
{
// Every character's frequency must be
// equal to the frequency of the most
// frequently occurring character
if (freq[i] > 0)
{
minAddition += Math.abs(maxFreq - freq[i]);
}
}
return minAddition;
}
let str = "geeksforgeeks";
let len = str.length;
document.write(minimumAddition(str, len));
</script>
Producción:
15
Publicación traducida automáticamente
Artículo escrito por AshaRamMeena y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA