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:
Python3
# Python3 Program of the
# above approach
# Function to find the minimum
# characters to be removed from
# the string
def getMinimumRemoval(str):
n = len(str)
# Initialize answer by N
ans = n
# If length is even
if(n % 2 == 0):
# Frequency array for odd
# and even indices
freqEven = {}
freqOdd = {}
for ch in range(ord('a'),
ord('z') + 1):
freqEven[chr(ch)] = 0
freqOdd[chr(ch)] = 0
# Store the frequency of the
# characters at even and odd
# indices
for i in range(n):
if(i % 2 == 0):
if str[i] in freqEven:
freqEven[str[i]] += 1
else:
if str[i] in freqOdd:
freqOdd[str[i]] += 1
# Stores the most occurring
# frequency for even and
# odd indices
evenMax = 0
oddMax = 0
for ch in range(ord('a'),
ord('z') + 1):
evenMax = max(evenMax,
freqEven[chr(ch)])
oddMax = max(oddMax,
freqOdd[chr(ch)])
# Update the answer
ans = ans - evenMax - oddMax
# If length is odd
else:
# Stores the frequency of the
# characters of the string
freq = {}
for ch in range('a','z'):
freq[chr(ch)] = 0
for i in range(n):
if str[i] in freq:
freq[str[i]] += 1
# Stores the most occurring
# characterin the string
strMax = 0
for ch in range('a','z'):
strMax = max(strMax,
freq[chr(ch)])
# Update the answer
ans = ans - strMax
return ans
# Driver Code
str = "geeksgeeks"
print(getMinimumRemoval(str))
# This code is contributed by avanitrachhadiya2155
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