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:
Java
// Java program of the
// above approach
class GFG{
// Function to find the minimum
// characters to be removed from
// the string
public static 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
int[] freqEven = new int[128];
int[] freqOdd = new int[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.charAt(i)]++;
}
else
{
freqOdd[str.charAt(i)]++;
}
}
// Stores the most occurring frequency
// for even and odd indices
int evenMax = 0, oddMax = 0;
for(char chr = 'a'; chr <= 'z'; chr++)
{
evenMax = Math.max(evenMax,
freqEven[chr]);
oddMax = Math.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
int[] freq = new int[128];
for(int i = 0; i < n; i++)
{
freq[str.charAt(i)]++;
}
// Stores the most occurring character
// in the string
int strMax = 0;
for(char chr = 'a'; chr <= 'z'; chr++)
{
strMax = Math.max(strMax, freq[chr]);
}
// Update the answer
ans = ans - strMax;
}
return ans;
}
// Driver code
public static void main(String[] args)
{
String str = "geeksgeeks";
System.out.print(getMinimumRemoval(str));
}
}
// This code is contributed by divyeshrabadiya07
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!
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