Minimice los cambios en 2 o 3 bits adyacentes para generar una string binaria de todos los 1

Dada una string binaria S que consta de 0 y 1 , la tarea es encontrar el número mínimo de vueltas requeridas para generar una string binaria de todos unos. El volteo se realiza en dos o tres índices adyacentes .

Ejemplos :

Entrada: S = “0010”
Salida: 2
Explicación: Las operaciones realizadas son: 00 10 -> 000 1 -> 1111 

Entrada: S = “0011110”
Salida: 3
Explicación: Las operaciones realizadas son: 00 11110 -> 1111 11 0 -> 1111 000  -> 1111111

Enfoque: La idea básica para resolver este problema es realizar volteos en los primeros 2 o 3 caracteres y agregar el resultado de la recursividad con las siguientes posiciones. Es solo una fuerza bruta recursiva de todas las posibilidades. Para cada índice de la string, intente dos volteretas adyacentes y tres volteretas adyacentes y luego recurra a ese subproblema. Una cosa importante es que el resultado es independiente del orden de los lanzamientos. 
Siga los pasos a continuación para resolver el problema:

1. Si la string dada no consta de ceros , devuelva «0» y si solo hay » 1 «, entonces no es necesario voltear.
2. Si la string dada, en cualquier momento se vuelve igual a » 00 » o » 000 «, entonces devuelva » 1 «, ya que solo se necesita 1 vuelta para que sean todos unos .
3. Necesitamos una lista para almacenar y comparar posibilidades mínimas en cualquier momento de la llamada recursiva.
4. Si la string comienza con » 0 » y la longitud de la string es mayor que 2 o 3 , volteamos los primeros dos o tres primeros caracteres y recursivamente llamamos nuevamente al siguiente índice.
5. Si las strings comienzan con » 1 «, lo eliminamos llamándolo recursivamente para el resto de la parte.
6. Ahora, en el caso de » 1 «, si » 0 » está presente en las primeras dos o tres posiciones, entonces cambiamos las primeras dos o tres posiciones y recursivamente llamamos al resto de la parte junto con agregar/agregar resultados a las listas.
7. Una vez que se completa un ciclo, devolvemos el mínimo de todos los elementos almacenados en la lista.

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

# Python program for the above approach
def minimumFlips(string):
  
    # No flip needed
    if "0" not in string:
        return 0
  
    # Flip the whole string at once
    if string in ("00", "000"):
        return 1
  
    # Flip 1st 2 / 3 characters
    def flip(n):
        return string[:n]\
               .translate({48: 49, 49: 48})\
               + string[n:]
  
    # For tracking minimum flips
    flips = [float('inf')]
  
    # Flip if string starts with zero
    if string.startswith("0"):
        # Flip first 2 and call recursively
        if len(string) > 2:
            flips.append(1 + minimumFlips(flip(2)[1:]))
        # Flip first 3 and call recursively
        if len(string) > 3:
            flips.append(1 + minimumFlips(flip(3)[1:]))
    # If string starts with "1"
    else:
        # No flip + recursion
        flips.append(minimumFlips(string[1:]))
  
        # Flip if zero is at 2nd position
        if "0" in string[:2]:
  
            # Flip first 2 and call recursively
            flips.append(1 + minimumFlips(flip(2)))
  
        # Flip if zero is at 2nd position
        if "0" in string[:3]:
  
            # Flip first 3 and call recursively
            flips.append(1 + minimumFlips(flip(3)))
    return min(flips)
  
# Driver code
if __name__ == "__main__":
    print(minimumFlips("0010"))

2

Tiempo Complejidad : O(N!)
Espacio Auxiliar : O(N)