Programa C++ para minimizar los caracteres que se cambiarán para hacer que la rotación izquierda y derecha de una string sea la misma

Dada una string S de alfabetos ingleses en minúsculas, la tarea es encontrar el número mínimo de caracteres que se cambiarán de modo que la rotación izquierda y derecha de la string sea la misma.

Ejemplos:

Entrada: S = “abcd”
Salida: 2
Explicación:
String después del desplazamiento a la izquierda: “bcda”
String después del desplazamiento a la derecha: “dabc”
Cambiando el carácter en la posición 3 a ‘a’ y el carácter en la posición 4 a ‘b’, la string se modifica a «abab».
Por lo tanto, tanto la rotación hacia la izquierda como hacia la derecha se convierte en «baba».

Entrada: S = “gfg”
Salida: 1
Explicación:
Después de actualizar el carácter en la posición 1 a ‘g’, la string se convierte en “ggg”.
Por lo tanto, la rotación izquierda y derecha son iguales.

Enfoque: La observación clave para resolver el problema es que cuando la longitud de la string es par, entonces todos los caracteres en el índice par y los caracteres en el índice impar deben ser iguales para que las rotaciones izquierda y derecha sean iguales. Para strings de longitud impar, todos los caracteres deben ser iguales. Siga los pasos a continuación para resolver el problema:

• Compruebe si la longitud de la string es par, entonces el número mínimo de caracteres que se cambiará es la longitud de la string, excluyendo la frecuencia del elemento que aparece más en los índices pares e impares.
• De lo contrario, si la longitud de la string es impar, el número mínimo de caracteres que se cambiará es la longitud de la string, excluyendo la frecuencia del carácter que aparece más en la string.
• Imprime el conteo final obtenido.

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

// C++ Program of the
// above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum
// characters to be removed from
// the string
int getMinimumRemoval(string str)
{
    int n = str.length();
 
    // Initialize answer by N
    int ans = n;
 
    // If length is even
    if (n % 2 == 0) {
 
        // Frequency array for odd
        // and even indices
        vector<int> freqEven(128);
        vector<int> freqOdd(128);
 
        // Store the frequency of the
        // characters at even and odd
        // indices
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                freqEven[str[i]]++;
            }
            else {
                freqOdd[str[i]]++;
            }
        }
 
        // Stores the most occurring frequency
        // for even and odd indices
        int evenMax = 0, oddMax = 0;
 
        for (char chr = 'a'; chr <= 'z'; chr++) {
 
            evenMax = max(evenMax, freqEven[chr]);
            oddMax = max(oddMax, freqOdd[chr]);
        }
 
        // Update the answer
        ans = ans - evenMax - oddMax;
    }
 
    // If length is odd
    else {
        // Stores the frequency of the
        // characters of the string
        vector<int> freq(128);
        for (int i = 0; i < n; i++) {
            freq[str[i]]++;
        }
 
        // Stores the most occurring character
        // in the string
        int strMax = 0;
        for (char chr = 'a'; chr <= 'z'; chr++) {
            strMax = max(strMax, freq[chr]);
        }
 
        // Update the answer
        ans = ans - strMax;
    }
 
    return ans;
}
 
// Driver Code
int main()
{
    string str = "geeksgeeks";
 
    cout << getMinimumRemoval(str);
}

6

Complejidad de tiempo: O(N), ya que estamos usando un bucle para atravesar N veces, por lo que nos costará O(N) tiempo 
Espacio auxiliar: O(1), ya que no estamos usando ningún espacio adicional.

¡ Consulte el artículo completo sobre Minimizar los caracteres que se cambiarán para hacer que la rotación izquierda y derecha de una string sea la misma para obtener más detalles!