Dada una string alfabética inferior “S” de tamaño N y un número entero K ; la tarea es encontrar el conteo de caracteres que permanecerán sin agrupar, luego de dividir la string dada en K grupos de caracteres distintos.
Ejemplos:
Entrada: S = “quedarseencasasalvavida”, K = 1
Salida: 6
Explicación:
En la string S los elementos que ocurren más de una vez son ‘e’ -> 3 veces, ‘s’ -> 3 veces, ‘a’ – > 2 veces, ‘i’ -> 2 veces y el resto de todos los elementos ocurre 1 vez cada uno.
Solo se formará un grupo como K = 1, por lo que solo una copia de estos elementos puede estar presente en el grupo y el resto de los elementos no pueden estar en el grupo,
por lo que los elementos que quedan fuera del grupo son 2 veces ‘ e’, 2 veces ‘s’, 1 vez ‘a’ y 1 vez ‘i’.
El total de elementos que quedan fuera es 6.
Entrada: S = «quedarse en casa salva la vida», K = 2
Salida: 2
Explicación:
En la string S, los elementos cuya ocurrencia es más de una vez son ‘e’ -> 3 veces, ‘s’ -> 3 veces, ‘a’ -> 2 veces, ‘i’ -> 2 veces y el resto ocurre todos los elementos 1 vez cada uno.
Como se pueden formar 2 grupos, un grupo contiene 1 copia de todos los elementos. El segundo grupo contendrá 1 copia de los elementos adicionales, es decir, ‘e’, ’s’, ‘a’ e ‘i’. Los elementos que se omitirán son 1 vez ‘e’ y 1 vez ‘s’.
Los elementos totales que quedarán fuera son 2.
Enfoque: La idea es utilizar el conteo de frecuencias .
- Cree una estructura de datos Hashing para almacenar la frecuencia de los caracteres ‘a’-‘z’.
- Encuentre la frecuencia inicial de cada carácter en la string dada y guárdela en la estructura de datos hash.
- Dado que un grupo puede contener solo 1 aparición de un carácter. Por lo tanto, disminuya K de la aparición de cada carácter en la estructura de datos hash.
- Ahora agregue las frecuencias restantes de los caracteres en la estructura de datos hash. Este será el número requerido de caracteres que permanecerán sin agrupar.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
void findUngroupedElement(string s,
int k)
{
int n = s.length();
// create array where
// index represents alphabets
int b[26];
for (int i = 0; i < 26; i++)
b[i] = 0;
// fill count of every
// alphabet to corresponding
// array index
for (int i = 0; i < n; i++) {
char p = s.at(i);
b[p - 'a'] += 1;
}
int sum = 0;
// count for every element
// how much is exceeding
// from no. of groups then
// sum them
for (int i = 0; i < 26; i++) {
if (b[i] > k)
sum += b[i] - k;
}
// print answer
cout << sum << endl;
}
// Driver code
int main()
{
string s = "stayinghomesaveslife";
int k = 1;
findUngroupedElement(s, k);
return 0;
}
Java
// Java code to implement the above approach
import java.util.*;
class GFG{
static void findUngroupedElement(String s,
int k)
{
int n = s.length();
// Create array where
// index represents alphabets
int []b = new int[26];
for(int i = 0; i < 26; i++)
b[i] = 0;
// Fill count of every
// alphabet to corresponding
// array index
for(int i = 0; i < n; i++)
{
char p = s.charAt(i);
b[p - 'a'] += 1;
}
int sum = 0;
// Count for every element
// how much is exceeding
// from no. of groups then
// sum them
for(int i = 0; i < 26; i++)
{
if (b[i] > k)
sum += b[i] - k;
}
// Print answer
System.out.println(sum);
}
// Driver code
public static void main(String srgs[])
{
String s = "stayinghomesaveslife";
int k = 1;
findUngroupedElement(s, k);
}
}
// This code is contributed by ANKITKUMAR34
Python3
# Python3 code to implement the above approach
def findUngroupedElement(s, k):
n = len(s);
# Create array where
# index represents alphabets
b = [0] * 26
# Fill count of every
# alphabet to corresponding
# array index
for i in range(n):
p = s[i]
b[ord(p) - ord('a')] += 1
sum = 0;
# Count for every element
# how much is exceeding
# from no. of groups then
# sum them
for i in range(26):
if (b[i] > k):
sum += b[i] - k
# Print answer
print(sum)
# Driver code
s = "stayinghomesaveslife"
k = 1
findUngroupedElement(s, k)
# This code is contributed by ANKITKUMAR34
C#
// C# code to implement the above approach
using System;
class GFG{
static void findUngroupedElement(String s,
int k)
{
int n = s.Length;
// Create array where
// index represents alphabets
int []b = new int[26];
for(int i = 0; i < 26; i++)
b[i] = 0;
// Fill count of every
// alphabet to corresponding
// array index
for(int i = 0; i < n; i++)
{
char p = s[i];
b[p - 'a'] += 1;
}
int sum = 0;
// Count for every element
// how much is exceeding
// from no. of groups then
// sum them
for(int i = 0; i < 26; i++)
{
if (b[i] > k)
sum += b[i] - k;
}
// Print answer
Console.WriteLine(sum);
}
// Driver code
public static void Main(String []srgs)
{
String s = "stayinghomesaveslife";
int k = 1;
findUngroupedElement(s, k);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript implementation of the above approach
function findUngroupedElement(s, k)
{
let n = s.length;
// Create array where
// index represents alphabets
let b = Array.from({length: 26}, (_, i) => 0);
for(let i = 0; i < 26; i++)
b[i] = 0;
// Fill count of every
// alphabet to corresponding
// array index
for(let i = 0; i < n; i++)
{
let p = s[i];
b[p.charCodeAt() - 'a'.charCodeAt()] += 1;
}
let sum = 0;
// Count for every element
// how much is exceeding
// from no. of groups then
// sum them
for(let i = 0; i < 26; i++)
{
if (b[i] > k)
sum += b[i] - k;
}
// Print answer
document.write(sum);
}
// Driver code
let s = "stayinghomesaveslife";
let k = 1;
findUngroupedElement(s, k);
// This code is contributed by code_hunt.
</script>
6
Complejidad de tiempo: O(N)
Complejidad de espacio auxiliar: O(26) que es equivalente a O(1)
Publicación traducida automáticamente
Artículo escrito por madarsh986 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA