Dada una string de letras en minúsculas y un número k, la tarea es imprimir el valor mínimo de la string después de eliminar los caracteres ‘k’. El valor de una string se define como la suma de los cuadrados de la cuenta de cada carácter distinto.
Por ejemplo, considere la string «saideep», aquí las frecuencias de los caracteres son s-1, a-1, i-1, e-2, d-1, p-1 y el valor de la string es 1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 2^2 = 9.
Complejidad del tiempo esperado: O(k*logn)
Ejemplos:
Input : str = abccc, K = 1 Output : 6 We remove c to get the value as 12 + 12 + 22 Input : str = aaab, K = 2 Output : 2
Preguntado en: Amazon
Una observación clara es que necesitamos eliminar caracteres con la mayor frecuencia. Un truco es el carácter ma
Una solución simple es usar la técnica de clasificación a través de todas las frecuencias más altas actuales reducir hasta k veces. Para Después de cada reducción, vuelva a ordenar la array de frecuencias.
Una mejor solución utilizada para Priority Queue, que tiene al elemento más alto en la parte superior.
- Inicializa la cola de prioridad vacía.
- Cuente la frecuencia de cada carácter y almacene en una array temporal.
- Retire K caracteres que tienen la frecuencia más alta de la cola.
- Finalmente, cuente la suma del cuadrado de cada elemento y devuélvalo.
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to find min sum of squares
// of characters after k removals
#include <bits/stdc++.h>
using namespace std;
const int MAX_CHAR = 26;
// Main Function to calculate min sum of
// squares of characters after k removals
int minStringValue(string str, int k)
{
int l = str.length(); // find length of string
// if K is greater than length of string
// so reduced string will become 0
if (k >= l)
return 0;
// Else find Frequency of each character and
// store in an array
int frequency[MAX_CHAR] = { 0 };
for (int i = 0; i < l; i++)
frequency[str[i] - 'a']++;
// Push each char frequency into a priority_queue
priority_queue<int> q;
for (int i = 0; i < MAX_CHAR; i++)
q.push(frequency[i]);
// Removal of K characters
while (k--) {
// Get top element in priority_queue,
// remove it. Decrement by 1 and again
// push into priority_queue
int temp = q.top();
q.pop();
temp = temp - 1;
q.push(temp);
}
// After removal of K characters find sum
// of squares of string Value
int result = 0; // Initialize result
while (!q.empty()) {
int temp = q.top();
result += temp * temp;
q.pop();
}
return result;
}
// Driver Code
int main()
{
string str = "abbccc"; // Input 1
int k = 2;
cout << minStringValue(str, k) << endl;
str = "aaab"; // Input 2
k = 2;
cout << minStringValue(str, k);
return 0;
}
Java
// Java program to find min sum of squares
// of characters after k removals
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Collections;
public class GFG {
static final int MAX_CHAR = 26;
// Main Function to calculate min sum of
// squares of characters after k removals
static int minStringValue(String str, int k)
{
int l = str.length(); // find length of string
// if K is greater than length of string
// so reduced string will become 0
if (k >= l)
return 0;
// Else find Frequency of each character and
// store in an array
int[] frequency = new int[MAX_CHAR];
for (int i = 0; i < l; i++)
frequency[str.charAt(i) - 'a']++;
// creating a priority queue with comparator
// such that elements in the queue are in
// descending order.
PriorityQueue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());
// Push each char frequency into a priority_queue
for (int i = 0; i < MAX_CHAR; i++) {
if (frequency[i] != 0)
q.add(frequency[i]);
}
// Removal of K characters
while (k != 0) {
// Get top element in priority_queue,
// remove it. Decrement by 1 and again
// push into priority_queue
q.add(q.poll() - 1);
k--;
}
// After removal of K characters find sum
// of squares of string Value
int result = 0; // Initialize result
while (!q.isEmpty()) {
result += q.peek() * q.poll();
}
return result;
}
// Driver Code
public static void main(String args[])
{
String str = "abbccc"; // Input 1
int k = 2;
System.out.println(minStringValue(str, k));
str = "aaab"; // Input 2
k = 2;
System.out.println(minStringValue(str, k));
}
}
// This code is contributed by Sumit Ghosh
Python 3
# Python3 program to find min sum of # squares of characters after k removals from queue import PriorityQueue MAX_CHAR = 26 # Main Function to calculate min sum of # squares of characters after k removals def minStringValue(str, k): l = len(str) # find length of string # if K is greater than length of string # so reduced string will become 0 if(k >= l): return 0 # Else find Frequency of each # character and store in an array frequency = [0] * MAX_CHAR for i in range(0, l): frequency[ord(str[i]) - 97] += 1 # Push each char frequency negative # into a priority_queue as the queue # by default is minheap q = PriorityQueue() for i in range(0, MAX_CHAR): q.put(-frequency[i]) # Removal of K characters while(k > 0): # Get top element in priority_queue # multiply it by -1 as temp is negative # remove it. Increment by 1 and again # push into priority_queue temp = q.get() temp = temp + 1 q.put(temp, temp) k = k - 1 # After removal of K characters find # sum of squares of string Value result = 0; # initialize result while not q.empty(): temp = q.get() temp = temp * (-1) result += temp * temp return result # Driver Code if __name__ == "__main__": str = "abbccc" k = 2 print(minStringValue(str, k)) str = "aaab" k = 2 print(minStringValue(str, k)) # This code is contributed # by Sairahul Jella
C#
// C# program to find min sum of squares
// of characters after k removals
using System;
using System.Collections.Generic;
class GFG {
static readonly int MAX_CHAR = 26;
// Main Function to calculate min sum of
// squares of characters after k removals
static int minStringValue(String str, int k)
{
int l = str.Length; // find length of string
// if K is greater than length of string
// so reduced string will become 0
if (k >= l)
return 0;
// Else find Frequency of each character and
// store in an array
int[] frequency = new int[MAX_CHAR];
for (int i = 0; i < l; i++)
frequency[str[i] - 'a']++;
// creating a priority queue with comparator
// such that elements in the queue are in
// descending order.
List<int> q = new List<int>();
// Push each char frequency into a priority_queue
for (int i = 0; i < MAX_CHAR; i++)
{
if (frequency[i] != 0)
q.Add(frequency[i]);
}
// Removal of K characters
while (k != 0)
{
q.Sort();
q.Reverse();
// Get top element in priority_queue,
// remove it. Decrement by 1 and again
// push into priority_queue
q.Add(q[0] - 1);
q.RemoveAt(0);
k--;
}
// After removal of K characters find sum
// of squares of string Value
int result = 0; // Initialize result
while (q.Count != 0)
{
result += q[0] * q[0];
q.RemoveAt(0);
}
return result;
}
// Driver Code
public static void Main(String []args)
{
String str = "abbccc"; // Input 1
int k = 2;
Console.WriteLine(minStringValue(str, k));
str = "aaab"; // Input 2
k = 2;
Console.WriteLine(minStringValue(str, k));
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// JavaScript program to find min sum of squares
// of characters after k removals
let MAX_CHAR = 26;
// Main Function to calculate min sum of
// squares of characters after k removals
function minStringValue(str,k)
{
let l = str.length; // find length of string
// if K is greater than length of string
// so reduced string will become 0
if (k >= l)
return 0;
// Else find Frequency of each character and
// store in an array
let frequency = new Array(MAX_CHAR);
for(let i=0;i<MAX_CHAR;i++)
frequency[i]=0;
for (let i = 0; i < l; i++)
frequency[str[i].charCodeAt(0) - 'a'.charCodeAt(0)]++;
// creating a priority queue with comparator
// such that elements in the queue are in
// descending order.
let q = [];
// Push each char frequency into a priority_queue
for (let i = 0; i < MAX_CHAR; i++) {
if (frequency[i] != 0)
q.push(frequency[i]);
}
q.sort(function(a,b){return b-a;});
// Removal of K characters
while (k != 0) {
// Get top element in priority_queue,
// remove it. Decrement by 1 and again
// push into priority_queue
q.push(q.shift() - 1);
q.sort(function(a,b){return b-a;});
k--;
}
// After removal of K characters find sum
// of squares of string Value
let result = 0; // Initialize result
while (q.length!=0) {
result += q[0] * q.shift();
}
return result;
}
// Driver Code
let str = "abbccc"; // Input 1
let k = 2;
document.write(minStringValue(str, k)+"<br>");
str = "aaab"; // Input 2
k = 2;
document.write(minStringValue(str, k)+"<br>");
// This code is contributed by unknown2108
</script>
Producción
6 2
Complejidad de tiempo: O(k*logn)
Enfoque eficiente:
Podemos resolverlo en una complejidad de tiempo O(N), ya que debemos ser codiciosos y siempre eliminar los caracteres de los alfabetos que tienen una frecuencia más alta.
Ejemplo: Sea str =”abbccc” y k =2 ahora, alphabetCount[1]=1;//for ‘a’ alphabetCount[2]=2;//for ‘b’ alphabetCount[3]=3;//for ‘c’ maximo=3 m[1]=1(solo a ocurre 1 vez) m[2]=1(solo b ocurre 2 veces) m[3]=1(solo c ocurre 3 veces) //k=2 máximo=3 entonces k=km[máximo]//k=k-1; así que ahora uno c tiene eliminaciones, por lo que las frecuencias son a = 1, b = 2, c = 2; así como la frecuencia de c disminuyó en uno, m [máximo] será cero y m [máximo-1] aumentará en m [máximo], así que actualice m [2] + = m [3], m [3] = 0; también maximu se reduce en uno, ya que se garantiza que existe una frecuencia menor que el máximo desde arriba. m[1]=1, m[2]=2, m[3]=0 y k=1; ahora m[máximo](es decir, m[2]=2>k), por lo que debemos eliminar parcialmente eliminar un carácter de b o c, de modo que m[1]=2 0,m[2]=1 ,m[3]= 0 yk=0; entonces, (1*1)*2 + (2*2)*1 + (3*3)*0 = 6//respuesta
Implementación:
C++
// C++ program to find min sum of squares
// of characters after k removals
#include <bits/stdc++.h>
using namespace std;
const int MAX_CHAR = 26;
// Main Function to calculate min sum of
// squares of characters after k removals
int minStringValue(string str, int k)
{
int alphabetCount[MAX_CHAR]= {0};
// Here the array stored frequency the number of
// occurrences in string m[frequency]=number of alphabets
// with frequency i.e, in our example abbccc m[1]=1(1
// a's occur),m[2]=1(2 b's occur),m[3]=1(3 c'soccur)
int m[str.length()] = { 0 };
for (int i = 0; i < str.length(); i++) {
alphabetCount[str[i] - 'a']++;
}
// Store the maximum
int maximum = 0;
for (int i = 0; i < MAX_CHAR; i++) {
m[alphabetCount[i]]++;
maximum = max(maximum, alphabetCount[i]);
}
while (k > 0) {
int z = m[maximum];
if (z <= k) {
// Remove one occurrence of alphabet from each
// with frequency as maximum.
// So we will have k-z more remove operations to
// perform as z is number of characters and we
// perform one removal from each of the alphabet
// with that frequency.
k = k - z;
// As we removed one occurrence from each the
// alphabets will no longer have the frequency
// of maximum their frequency will be decreased
// by one so add these number of alphabets to
// group with frequency one less than maximum.
// Remove them from maximum count.
m[maximum] = 0;
// Add those to frequency one less.
m[maximum - 1] += z;
// new maximum will be one less.
maximum--;
}
else {
// if all the elements of that frequency cannot
// be removed we should partially remove them.
m[maximum] -= k;
maximum--;
m[maximum] += k;
k = 0;
}
}
int ans = 0;
for (int i = 0; i < str.length(); i++) {
//(square of frequency)*(number of
// characters corresponding to that frequency)
ans += (i * i) * m[i];
}
return ans;
}
// Driver Code
int main()
{
string str = "abbccc"; // Input 1
int k = 2;
cout << minStringValue(str, k) << endl;
str = "aaab"; // Input 2
k = 2;
cout << minStringValue(str, k);
return 0;
}
// This code is contributed by Kasina Dheeraj.
Java
// Java program to find min sum of squares
// of characters after k removals
import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;
public class GFG {
static final int MAX_CHAR = 26;
// Main Function to calculate min sum of
// squares of characters after k removals
static int minStringValue(String str, int k)
{
int[] alphabetCount = new int[MAX_CHAR];
// Here the array stored frequency the number of
// occurrences in string m[frequency]=number of
// alphabets with frequency i.e, in our example
// abbccc m[1]=1(1 a's occur),m[2]=1(2 b's
// occur),m[3]=1(3 c'soccur)
int[] m = new int[str.length()];
for (int i = 0; i < str.length(); i++) {
alphabetCount[str.charAt(i) - 'a']++;
}
// Store the maximum
int maximum = 0;
for (int i = 0; i < MAX_CHAR; i++) {
m[alphabetCount[i]]++;
maximum = Math.max(maximum, alphabetCount[i]);
}
while (k > 0) {
int z = m[maximum];
if (z <= k) {
// Remove one occurrence of alphabet from
// each with frequency as maximum. So we
// will have k-z more remove operations to
// perform as z is number of characters and
// we perform one removal from each of the
// alphabet with that frequency.
k = k - z;
// As we removed one occurrence from each the
// alphabets will no longer have the
// frequency of maximum their frequency will
// be decreased by one so add these number
// of alphabets to group with frequency one
// less than maximum. Remove them from
// maximum count.
m[maximum] = 0;
// Add those to frequency one less.
m[maximum - 1] += z;
// new maximum will be one less.
maximum--;
}
else {
// if all the elements of that frequency
// cannot be removed we should partially
// remove them.
m[maximum] -= k;
maximum--;
m[maximum] += k;
k = 0;
}
}
int ans = 0;
for (int i = 0; i < str.length(); i++) {
//(square of frequency)*(number of
// characters corresponding to that frequency)
ans += (i * i) * m[i];
}
return ans;
}
// Driver Code
public static void main(String args[])
{
String str = "abbccc"; // Input 1
int k = 2;
System.out.println(minStringValue(str, k));
str = "aaab"; // Input 2
k = 2;
System.out.println(minStringValue(str, k));
}
}
// This code is contributed by Kasina Dheeraj.
Python3
# Python program to find min sum of squares
# of characters after k removals
MAX_CHAR = 26
# Main Function to calculate min sum of
# squares of characters after k removals
def minStringValue(str, k):
alphabetCount =[]
for i in range(MAX_CHAR):
alphabetCount.append(0)
# Here the array stored frequency the number of
# occurrences in string m[frequency]=number of alphabets
# with frequency i.e, in our example abbccc m[1]=1(1
# a's occur),m[2]=1(2 b's occur),m[3]=1(3 c'soccur)
m = []
for i in range(len(str)):
m.append(0)
for i in range(len(str)):
alphabetCount[ord(str[i]) - ord('a')] += 1
# Store the maximum
maximum = 0
for i in range(MAX_CHAR):
m[alphabetCount[i]] += 1
maximum = max(maximum, alphabetCount[i])
while (k > 0):
z = m[maximum]
if z <= k:
# Remove one occurrence of alphabet from each
# with frequency as maximum.
# So we will have k-z more remove operations to
# perform as z is number of characters and we
# perform one removal from each of the alphabet
# with that frequency.
k = k - z
# As we removed one occurrence from each the
# alphabets will no longer have the frequency
# of maximum their frequency will be decreased
# by one so add these number of alphabets to
# group with frequency one less than maximum.
# Remove them from maximum count.
m[maximum] = 0
# Add those to frequency one less.
m[maximum - 1] += z
# new maximum will be one less.
maximum -= 1
else:
# if all the elements of that frequency cannot
# be removed we should partially remove them.
m[maximum] -= k
maximum -= 1
m[maximum] += k
k = 0
ans = 0
for i in range(len(str)):
# (square of frequency)*(number of
# characters corresponding to that frequency)
ans = ans + (i * i) * m[i]
return ans
# Driver Code
str = "abbccc" # Input 1
k = 2
print(minStringValue(str, k))
str = "aaab" # Input 2
k = 2
print(minStringValue(str, k))
# This code is contributed by Abhijeet Kumar(abhijeet19403)
C#
// C# program to find min sum of squares
// of characters after k removals
using System;
public static class GFG {
static int MAX_CHAR = 26;
// Main Function to calculate min sum of
// squares of characters after k removals
static int minStringValue(string str, int k)
{
int[] alphabetCount = new int[MAX_CHAR];
// Here the array stored frequency the number of
// occurrences in string m[frequency]=number of
// alphabets with frequency i.e, in our example
// abbccc m[1]=1(1 a's occur),m[2]=1(2 b's
// occur),m[3]=1(3 c'soccur)
int[] m = new int[str.Length];
for (int i = 0; i < str.Length; i++) {
alphabetCount[str[i] - 'a']++;
}
// Store the maximum
int maximum = 0;
for (int i = 0; i < MAX_CHAR; i++) {
m[alphabetCount[i]]++;
maximum = Math.Max(maximum, alphabetCount[i]);
}
while (k > 0) {
int z = m[maximum];
if (z <= k) {
// Remove one occurrence of alphabet from
// each with frequency as maximum. So we
// will have k-z more remove operations to
// perform as z is number of characters and
// we perform one removal from each of the
// alphabet with that frequency.
k = k - z;
// As we removed one occurrence from each
// the alphabets will no longer have the
// frequency of maximum their frequency will
// be decreased by one so add these number
// of alphabets to group with frequency one
// less than maximum. Remove them from
// maximum count.
m[maximum] = 0;
// Add those to frequency one less.
m[maximum - 1] += z;
// new maximum will be one less.
maximum--;
}
else {
// if all the elements of that frequency
// cannot be removed we should partially
// remove them.
m[maximum] -= k;
maximum--;
m[maximum] += k;
k = 0;
}
}
int ans = 0;
for (int i = 0; i < str.Length; i++) {
//(square of frequency)*(number of
// characters corresponding to that frequency)
ans += (i * i) * m[i];
}
return ans;
}
// Driver Code
public static void Main()
{
string str = "abbccc"; // Input 1
int k = 2;
Console.Write(minStringValue(str, k));
Console.Write("\n");
str = "aaab"; // Input 2
k = 2;
Console.Write(minStringValue(str, k));
}
}
// This code is contributed by Aarti_Rathi
Javascript
<script>
// JavaScript program to find min sum of squares
// of characters after k removals
let MAX_CHAR = 26;
// Main Function to calculate min sum of
// squares of characters after k removals
function minStringValue(str,k)
{
var alphabetCount = new Array(MAX_CHAR).fill(0);
// Here the array stored frequency the number of
// occurrences in string m[frequency]=number of alphabets
// with frequency i.e, in our example abbccc m[1]=1(1
// a's occur),m[2]=1(2 b's occur),m[3]=1(3 c'soccur)
var m = new Array(str.length).fill(0);
var i;
for (i = 0; i < str.length; i++) {
alphabetCount[str.charCodeAt(i) - 97]++;
}
// Store the maximum
var maximum = 0;
for (i = 0; i < MAX_CHAR; i++) {
m[alphabetCount[i]]++;
maximum = Math.max(maximum, alphabetCount[i]);
}
while (k > 0) {
var z = m[maximum];
if (z <= k) {
// Remove one occurrence of alphabet from each
// with frequency as maximum.
// So we will have k-z more remove operations to
// perform as z is number of characters and we
// perform one removal from each of the alphabet
// with that frequency.
k = k - z;
// As we removed one occurrence from each the
// alphabets will no longer have the frequency
// of maximum their frequency will be decreased
// by one so add these number of alphabets to
// group with frequency one less than maximum.
// Remove them from maximum count.
m[maximum] = 0;
// Add those to frequency one less.
m[maximum - 1] += z;
// new maximum will be one less.
maximum--;
}
else {
// if all the elements of that frequency cannot
// be removed we should partially remove them.
m[maximum] -= k;
maximum--;
m[maximum] += k;
k = 0;
}
}
var ans = 0;
for (i = 0; i < str.length; i++) {
//(square of frequency)*(number of
// characters corresponding to that frequency)
ans += (i * i) * m[i];
}
return ans;
}
// Driver Code
let str = "abbccc"; // Input 1
let k = 2;
document.write(minStringValue(str, k)+"<br>");
str = "aaab"; // Input 2
k = 2;
document.write(minStringValue(str, k)+"<br>");
// This code is contributed by aditya942003patil
</script>
Producción
6 2
Complejidad de tiempo: O(N)
Complejidad de espacio: O(N)
Este artículo es una contribución del Sr. Somesh Awasthi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA