Dada una string S de longitud N. La tarea es encontrar el número mínimo de pasos necesarios en las strings, de modo que tenga exactamente K alfabetos diferentes, todos con la misma frecuencia.
Nota : en un solo paso, podemos cambiar una letra a cualquier otra letra.
Ejemplos:
Input: S = "abbc", N = 4, K = 2 Output: 1 In one step convert 'c' to 'a'. Hence string has two different letters a and b both occurring 2 times.
Enfoque :
- Compruebe si K divide a N, entonces solo es posible convertir la string dada, de lo contrario no.
- Mantenga el recuento de todos los alfabetos presentes en la string S, en una array A.
- Evalúe E = N/K , la frecuencia con la que los alfabetos estarán presentes en la string final.
- Separe los alfabetos con frecuencia mayor o igual a E y menor a E en dos partes.
- Mantenga el número de pasos necesarios para que cada alfabeto convierta su cuenta a E, ordene estos vectores obtenidos en el paso anterior.
- Por último, aprovecha todas las posibilidades para elegir:
Set 1 : 0 Set 2 : K Set 1 : 1 Set 2 : K-1 .... so on
- Mantenga una variable ans para calcular el número mínimo de pasos entre todas las posibilidades en el paso 6.
- Digamos que L1 es el número de operaciones requeridas en el Conjunto 1, L2 es el número de operaciones requeridas en el conjunto 2. Luego, el total de operaciones requeridas es el máximo de L1, L2. Como supongamos que ‘a’ se requiere uno menos en la string, mientras que ‘b’ se requiere uno más de lo que podemos cambiar ‘a’ a ‘b’, reduciendo así el número de pasos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to convert the given string
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum number of
// operations to convert the given string
void minOperation(string S, int N, int K)
{
// Check if N is divisible by K
if (N % K) {
cout << "Not Possible" << endl;
return;
}
// Array to store frequency of characters
// in given string
int count[26] = { 0 };
for (int i = 0; i < N; i++) {
count[S[i] - 97]++;
}
int E = N / K;
vector<int> greaterE;
vector<int> lessE;
for (int i = 0; i < 26; i++) {
// Two arrays with number of operations
// required
if (count[i] < E)
lessE.push_back(E - count[i]);
else
greaterE.push_back(count[i] - E);
}
sort(greaterE.begin(), greaterE.end());
sort(lessE.begin(), lessE.end());
int mi = INT_MAX;
for (int i = 0; i <= K; i++) {
// Checking for all possibility
int set1 = i;
int set2 = K - i;
if (greaterE.size() >= set1 && lessE.size() >= set2) {
int step1 = 0;
int step2 = 0;
for (int j = 0; j < set1; j++)
step1 += greaterE[j];
for (int j = 0; j < set2; j++)
step2 += lessE[j];
mi = min(mi, max(step1, step2));
}
}
cout << mi << endl;
}
// Driver Code
int main()
{
string S = "accb";
int N = S.size();
int K = 2;
minOperation(S, N, K);
return 0;
}
Java
// JAVA program to convert the given string
import java.util.*;
class GFG
{
// Function to find the minimum number of
// operations to convert the given string
static void minOperation(String S, int N, int K)
{
// Check if N is divisible by K
if (N % K != 0)
{
System.out.println("Not Possible");
}
else
{
// Array to store frequency of characters
// in given string
int [] count = new int[26];
for (int i = 0; i < N; i++)
{
count[(S.charAt(i) - 97)]++;
}
int E = N / K;
Vector<Integer> greaterE = new Vector<>();
Vector<Integer> lessE = new Vector<>();
for (int i = 0; i < 26; i++)
{
// Two arrays with number of operations
// required
if (count[i] < E)
lessE.add(E - count[i]);
else
greaterE.add(count[i] - E);
}
Collections.sort(greaterE);
Collections.sort(lessE);
int mi = Integer.MAX_VALUE;
for (int i = 0; i <= K; i++)
{
// Checking for all possibility
int set1 = i;
int set2 = K - i;
if (greaterE.size() >= set1 &&
lessE.size() >= set2)
{
int step1 = 0;
int step2 = 0;
for (int j = 0; j < set1; j++)
step1 += greaterE.get(j);
for (int j = 0; j < set2; j++)
step2 += lessE.get(j);
mi = Math.min(mi, Math.max(step1, step2));
}
}
System.out.println(mi);
}
}
// Driver Code
public static void main (String[] args)
{
String S = "accb";
int N = S.length();
int K = 2;
minOperation(S, N, K);
}
}
// This code is contributed by ihritik
Python3
# Python3 program to convert the given string
# Function to find the minimum number of
# operations to convert the given string
def minOperation(S, N, K):
# Check if N is divisible by K
if N % K:
print("Not Possible")
return
# Array to store frequency of
# characters in given string
count = [0] * 26
for i in range(0, N):
count[ord(S[i]) - 97] += 1
E = N // K
greaterE = []
lessE = []
for i in range(0, 26):
# Two arrays with number of
# operations required
if count[i] < E:
lessE.append(E - count[i])
else:
greaterE.append(count[i] - E)
greaterE.sort()
lessE.sort()
mi = float('inf')
for i in range(0, K + 1):
# Checking for all possibility
set1, set2 = i, K - i
if (len(greaterE) >= set1 and
len(lessE) >= set2):
step1, step2 = 0, 0
for j in range(0, set1):
step1 += greaterE[j]
for j in range(0, set2):
step2 += lessE[j]
mi = min(mi, max(step1, step2))
print(mi)
# Driver Code
if __name__ == "__main__":
S = "accb"
N = len(S)
K = 2
minOperation(S, N, K)
# This code is contributed by Rituraj Jain
C#
// C# program to convert the given string
using System;
using System.Collections.Generic;
class GFG
{
// Function to find the minimum number of
// operations to convert the given string
static void minOperation(string S, int N, int K)
{
// Check if N is divisible by K
if (N % K != 0)
{
Console.WriteLine("Not Possible");
}
else
{
// Array to store frequency of characters
// in given string
int [] count = new int[26];
for (int i = 0; i < N; i++)
{
count[(S[i] - 97)]++;
}
int E = N / K;
List<int> greaterE = new List<int>();
List<int> lessE = new List<int>();
for (int i = 0; i < 26; i++)
{
// Two arrays with number of operations
// required
if (count[i] < E)
lessE.Add(E - count[i]);
else
greaterE.Add(count[i] - E);
}
greaterE.Sort();
lessE.Sort();
int mi = Int32.MaxValue;
for (int i = 0; i <= K; i++)
{
// Checking for all possibility
int set1 = i;
int set2 = K - i;
if (greaterE.Count >= set1 &&
lessE.Count >= set2)
{
int step1 = 0;
int step2 = 0;
for (int j = 0; j < set1; j++)
step1 += greaterE[j];
for (int j = 0; j < set2; j++)
step2 += lessE[j];
mi = Math.Min(mi, Math.Max(step1, step2));
}
}
Console.WriteLine(mi);
}
}
// Driver Code
public static void Main ()
{
string S = "accb";
int N = S.Length;
int K = 2;
minOperation(S, N, K);
}
}
// This code is contributed by ihritik
Javascript
<script>
// Javascript program to convert the given string
// Function to find the minimum number of
// operations to convert the given string
function minOperation(S, N, K)
{
// Check if N is divisible by K
if (N % K) {
document.write( "Not Possible" );
return;
}
// Array to store frequency of characters
// in given string
var count = Array(26).fill(0);
for (var i = 0; i < N; i++) {
count[S[i].charCodeAt(0) - 97]++;
}
var E = N / K;
var greaterE = [];
var lessE = [];
for (var i = 0; i < 26; i++) {
// Two arrays with number of operations
// required
if (count[i] < E)
lessE.push(E - count[i]);
else
greaterE.push(count[i] - E);
}
greaterE.sort();
lessE.sort();
var mi = 1000000000;
for (var i = 0; i <= K; i++) {
// Checking for all possibility
var set1 = i;
var set2 = K - i;
if (greaterE.length >= set1 && lessE.length >= set2) {
var step1 = 0;
var step2 = 0;
for (var j = 0; j < set1; j++)
step1 += greaterE[j];
for (var j = 0; j < set2; j++)
step2 += lessE[j];
mi = Math.min(mi, Math.max(step1, step2));
}
}
document.write( mi );
}
// Driver Code
var S = "accb";
var N = S.length;
var K = 2;
minOperation(S, N, K);
</script>
Producción:
1
Complejidad temporal : O(1) Como el valor de k es constante, se desprecia en la complejidad temporal.
Espacio Auxiliar : O(1) Como estamos tomando un espacio constante de tamaño 26.