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

Rotación significa que tenemos que mover cada personaje hacia adelante o hacia atrás. La dirección hacia adelante significa rotación hacia la derecha (o en el sentido contrario a las agujas del reloj) y la dirección hacia atrás significa rotación hacia la izquierda (o en el sentido de las agujas del reloj).

En este problema, hemos dado una cadena de tamaño n. Nuestra tarea es encontrar el número mínimo de caracteres a cambiar para comprobar si es posible hacer que la rotación hacia la izquierda y hacia la derecha de una cadena sea la misma.

Veamos ejemplos con explicaciones a continuación para entender mejor el problema.

Entrada 1

str = "wxyz"

Salida 1

Explicación

La rotación izquierda de la cuerda es xyzw.

La rotación derecha de la cuerda es zwxy.

Entonces, según la observación, cambie el carácter en la posición de 0 str[0]=w a y y en la posición de 3 str[3]=z a x. La cadena se convierte en yxyx.

Por lo tanto, la respuesta es 2 ya que las cadenas de rotación izquierda y derecha se vuelven xyxy.

Entrada 2

str = "aka"

Salida 2

Explicación

La rotación izquierda de la cuerda es aak.

La rotación correcta de la cuerda es kaa.

Entonces, según la observación, cambie el carácter en la posición de 1 str[1]=k a a. La cuerda se vuelve aaa.

Por lo tanto, la respuesta es 1 ya que las cadenas de rotación izquierda y derecha se vuelven aaa.

Acercarse

Después de ver el ejemplo de la cadena anterior, pasemos al método.

La idea de este enfoque se basa en la observación. La observación tiene dos puntos:

cuando tenemos una cadena de longitud par, todos los caracteres presentes en la cadena en el índice par y en el índice impar deben ser iguales para que las cadenas giradas hacia la derecha y hacia la izquierda sean iguales.
Cuando tenemos una cadena de longitud impar, todos los caracteres presentes en la cadena deben ser iguales para que las cadenas giradas hacia la derecha y hacia la izquierda sean iguales.

Veamos el código a continuación para comprender mejor el enfoque anterior.

Ejemplo

# Function to find the minimum characters to be removed from the string
def getMinimumChange(str, n):
   # Initialize answer by N in variable minNum
   minChanges = n
   # If the length of the string is even
   if (n % 2 == 0):
      # Created frequency array for Even index
      freqEvenIdx = {}
      # Created frequency array for odd index
      freqOddIdx = {}
      # Traverse for loop to intialize both the frequency array freqEvenddIdx and freqOddIdx to 0
      for ch in range(ord('a'), ord('z') + 1):
         freqEvenIdx[chr(ch)] = 0
         freqOddIdx[chr(ch)] = 0
      # at odd and even index
      for i in range(n):
         if (i % 2 == 0):
            if str[i] in freqEvenIdx:
               freqEvenIdx[str[i]] += 1
         else:
            if str[i] in freqOddIdx:
               freqOddIdx[str[i]] += 1
      # Create variable evenIdxMax and OddIdxMax to store maximum frequency of even place character and odd place character respectively
      evenIdxMax = 0
      oddIdxMax = 0
      # Traverse for loop from a to z to update variable evenIdxMax and OddIdxMax
      for ch in range(ord('a'), ord('z') + 1):
         evenIdxMax = max(evenIdxMax, freqEvenIdx[chr(ch)])
         oddIdxMax = max(oddIdxMax, freqOddIdx[chr(ch)])
      # Update the answerin variable minChanges
      minChanges = minChanges - evenIdxMax - oddIdxMax
   # If the length of the string is odd
   else:
      # Create array to store frequecy of character of the string
      freq = {}
      #  initialize the the freq array
      for ch in range('a', 'z'):
         freq[chr(ch)] = 0
      # Stores the frequency of the characters of the string while traversing the string
      for i in range(n):
         if str[i] in freq:
            freq[str[i]] += 1
      # Stores the maximum freuency of character of the string in variable freqMax
      freqMax = 0
      #  Traverse the for loop to update freqMax
      for ch in range('a', 'z'):
         freqMax = max(freqMax, freq[chr(ch)])
      # Update the answer in variable minChanges
      minChanges = minChanges - freqMax
# Return final answer minChanges
   return minChanges
str = "wxyz"  # Given String
n = len(str)  # Getting size of the given string
# Call the function to get minimum number of changes to make left and right rotated string same
res = getMinimumChange(str, n)
# Print result
print(
   "The minimum number of changes to make the left and right rotated string same are: "
)
print(res)

Producción

The minimum number of changes to make the left and right rotated string same are: 
2

Complejidad del tiempo y el espacio

La complejidad temporal del código anterior es O (N), ya que atravesamos tanto el resorte como el número.

La complejidad espacial del código anterior es O(1), ya que no se utiliza espacio adicional para almacenar nada.

Donde N es el tamaño de la cuerda.

Conclusión