Minimice los cambios para hacer que todos los caracteres sean iguales cambiando vocal a consonante y viceversa

Dada una string str[] de caracteres en minúsculas, la tarea es hacer que todos los caracteres de la string sean iguales en el número mínimo de operaciones, de modo que en cada operación elija una vocal y la cambie a una consonante o viceversa.

Ejemplos:

Entrada: str[] = “geeksforgeeks”
Salida: 10
Explicación: Para que todos los caracteres sean iguales, realice los siguientes cambios: 

1. Cambia ‘o’ a una consonante (digamos) ‘z’ y luego a ‘e’
2. Cambia cualquier otra consonante (‘g’, ‘k’, ‘s’, ‘f’, ‘r’, ) a ‘e’

Esto da como resultado la string str = “eeeeeeeeeeeeee” y el número total de operaciones realizadas es 10.

Entrada: str[] = “codificación”
Salida: 6

Planteamiento: Del problema se puede deducir que para cambiar una consonante a vocal se requiere 1 operación y para cambiar una vocal a vocal o una consonante a consonante se requieren 2 pasos ya que se necesita cambiar una vocal a una consonante y luego nuevamente a una vocal en caso de cambiar una vocal a una vocal o cambiar una consonante a una vocal y luego nuevamente a una consonante en caso de cambiar una consonante a una consonante. La idea sería mantener dos variables:

• Cv = el costo de cambiar todos los caracteres al máximo de vocales que ocurren = no. de consonantes + (número total de vocales – frecuencia de la vocal máxima que aparece) * 2
• Cc = el costo de cambiar todos los caracteres a la consonante máxima que ocurre = no. de vocales + (número total de consonantes – frecuencia de la consonante máxima que aparece) * 2

Ahora, el mínimo de estos 2, es decir, min(Cv, Cc) dará el número mínimo requerido de pasos en los que podemos transformar la string. Siga los pasos a continuación para resolver el problema:

• Inicialice la variable ans, vocales y consonantes como 0 para almacenar la respuesta, el número de vocales y el número de consonantes.
• Inicialice 2 variables max_vocales y max_consonants como INT_MIN para encontrar la vocal máxima y la consonante máxima en la string dada.
• Inicialice 2 unordered_map<char, int> freq_vowels[] y freq_consonant[] para almacenar la frecuencia de vocales y consonantes.
• Iterar sobre el rango [0, N) usando la variable i y realizar los siguientes pasos:
  • Si el carácter actual es una vocal, aumente el recuento de vocales en 1 y su frecuencia en el mapa en 1 ; de lo contrario, hágalo para la consonante.
• Recorra ambos mapas unordered_map y encuentre la vocal y la consonante máximas que ocurren.
• Usando la fórmula anterior, calcule el ans.
• Después de realizar los pasos anteriores, imprima el valor de ans como respuesta.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum number
// of steps to make all characters equal
int operations(string s)
{
 
    // Initializing the variables
    int ans = 0;
    int vowels = 0, consonants = 0;
    int max_vowels = INT_MIN;
    int max_consonants = INT_MIN;
 
    // Store the frequency
    unordered_map<char, int> freq_consonants;
    unordered_map<char, int> freq_vowels;
 
    // Iterate over the string
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == 'a' or s[i] == 'e' or s[i] == 'i'
            or s[i] == 'o' or s[i] == 'u') {
 
            // Calculate the total
            // number of vowels
            vowels += 1;
 
            // Storing frequency of
            // each vowel
            freq_vowels[s[i]] += 1;
        }
        else {
 
            // Count the consonants
            consonants += 1;
 
            // Storing the frequency of
            // each consonant
            freq_consonants[s[i]] += 1;
        }
    }
 
    // Iterate over the 2 maps
    for (auto it = freq_consonants.begin();
         it != freq_consonants.end(); it++) {
 
        // Maximum frequency of consonant
        max_consonants = max(
            max_consonants,
            it->second);
    }
    for (auto it = freq_vowels.begin();
         it != freq_vowels.end(); it++) {
 
        // Maximum frequency of vowel
        max_vowels
            = max(max_vowels,
                  it->second);
    }
 
    // Find the result
    ans = min((2 * (vowels - max_vowels)
               + consonants),
              (2 * (consonants - max_vowels)
               + consonants));
 
    return ans;
}
 
// Driver Code
int main()
{
    string S = "geeksforgeeks";
    cout << operations(S);
 
    return 0;
}

# Python 3 program for the above approach
import sys
from collections import defaultdict
 
# Function to find the minimum number
# of steps to make all characters equal
def operations(s):
 
    # Initializing the variables
    ans = 0
    vowels = 0
    consonants = 0
    max_vowels = -sys.maxsize-1
    max_consonants = -sys.maxsize-1
 
    # Store the frequency
    freq_consonants = defaultdict(int)
    freq_vowels = defaultdict(int)
 
    # Iterate over the string
    for i in range(len(s)):
        if (s[i] == 'a' or s[i] == 'e' or s[i] == 'i'
                or s[i] == 'o' or s[i] == 'u'):
 
            # Calculate the total
            # number of vowels
            vowels += 1
 
            # Storing frequency of
            # each vowel
            freq_vowels[s[i]] += 1
 
        else:
 
            # Count the consonants
            consonants += 1
 
            # Storing the frequency of
            # each consonant
            freq_consonants[s[i]] += 1
 
    # Iterate over the 2 maps
    for it in freq_consonants:
 
        # Maximum frequency of consonant
        max_consonants = max(
            max_consonants,
            freq_consonants[it])
 
    for it in freq_vowels:
 
        # Maximum frequency of vowel
        max_vowels = max(max_vowels,
                         freq_vowels[it])
 
    # Find the result
    ans = min((2 * (vowels - max_vowels)
               + consonants),
              (2 * (consonants - max_vowels)
               + consonants))
 
    return ans
 
# Driver Code
if __name__ == "__main__":
 
    S = "geeksforgeeks"
    print(operations(S))
 
    # This code is contributed by ukasp.

<script>
        // JavaScript Program to implement
        // the above approach
 
        // Function to find the minimum number
        // of steps to make all characters equal
        function operations(s) {
 
            // Initializing the variables
            let ans = 0;
            let vowels = 0, consonants = 0;
            let max_vowels = Number.MIN_VALUE;
            let max_consonants = Number.MIN_VALUE;
 
            // Store the frequency
            let freq_consonants = new Map();
            let freq_vowels = new Map();
 
            // Iterate over the string
            for (let i = 0; i < s.length; i++)
            {
                if (s.charAt(i) == 'a' || s.charAt(i) == 'e' || s.charAt(i) == 'i'
                    || s.charAt(i) == 'o' || s.charAt(i) == 'u') {
 
                    // Calculate the total
                    // number of vowels
                    vowels += 1;
 
                    // Storing frequency of
                    // each vowel
                    if (freq_vowels.has(s.charAt(i))) {
                        freq_vowels.set(s.charAt(i), freq_vowels.get(s.charAt(i)) + 1)
                    }
                    else {
                        freq_vowels.set(s.charAt(i), 1);
                    }
 
                }
                else {
 
                    // Count the consonants
                    consonants += 1;
 
                    // Storing the frequency of
                    // each consonant
                    if (freq_consonants.has(s.charAt(i))) {
                        freq_consonants.set(s.charAt(i), freq_consonants.get(s.charAt(i)) + 1)
                    }
                    else {
                        freq_consonants.set(s.charAt(i), 1);
                    }
 
                }
            }
 
            // Iterate over the 2 maps
            for (let [key, value] of freq_consonants) {
 
                // Maximum frequency of consonant
                max_consonants = Math.max(
                    max_consonants,
                    value);
            }
            for (let [key1, value1] of freq_vowels) {
 
                // Maximum frequency of vowel
                max_vowels
                    = Math.max(max_vowels,
                        value1);
            }
 
            // Find the result
            ans = Math.min((2 * (vowels - max_vowels)
                + consonants),
                (2 * (consonants - max_vowels)
                    + consonants));
 
            return ans;
        }
 
        // Driver Code
        let S = "geeksforgeeks";
        document.write(operations(S));
 
     // This code is contributed by Potta Lokesh
    </script>

10

Complejidad temporal: O(N)
Espacio auxiliar: O(N)