Se requieren cambios mínimos de substrings de 1 para agrupar todos los 1 en una string binaria dada

Dada una string binaria S de longitud N , la tarea es imprimir el número mínimo de índices, las substrings que consisten solo en 1 deben cambiarse de modo que todos los 1 presentes en la string se agrupen.

Ejemplos:

Entrada: S = “00110111011”
Salida: 2
Explicación:  
Operación 1: Desplace la substring {S[2], S[3]} ( indexación basada en 0 ) a la derecha y colóquela entre S[4] y S[5]. Ahora, S se modifica a “00011111011”. 
Operación 2: Desplace la substring {S[10], S[11]} a la izquierda y colóquela entre S[7] y S[8]. Ahora, S se modifica a «00011111110». 
Por lo tanto, se requiere cambiar 2 substrings.

Entrada: S = “1001001”
Salida: 4
Explicación:  
Operación 1: Desplace ‘1’ en S[0] a la derecha dos índices y colóquelo entre S[2] y S[3]. Ahora, S se modifica a “0011001”. 
Operación 2: Desplace ‘1’ en S[6] a la izquierda dos índices y colóquelo entre S[3] y S[4]. Ahora, S se modifica a “0011100”. 
Por lo tanto, se requiere cambiar 4 substrings.

Enfoque: El problema se puede resolver observando que el número mínimo de operaciones requeridas es igual al número de 0 s presentes entre cualquier par de 1 s consecutivos. Siga los pasos a continuación para resolver el problema:

1. Itere sobre los caracteres de la string y busque la primera y la última ocurrencia del carácter ‘1’ y guárdelo en la variable, digamos firstOne y lastOne respectivamente.
2. Recorra el rango [firstOne, lastOne] y cuente el número de ‘0’ presentes en la substring {S[firstOne], .. , S[lastOne]} e imprímalo como la salida requerida.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count indices substrings
// of 1s need to be shifted such that
// all 1s in the string are grouped together
void countShifts(string str)
{
    // Stores first occurrence of '1'
    int firstOne = -1;
 
    // Stores last occurrence of '1'
    int lastOne = -1;
 
    // Count of 0s between firstOne and lastOne
    int count = 0;
 
    // Traverse the string to find the
    // first and last occurrences of '1'
    for (int i = 0; i < str.length(); i++) {
        if (str[i] == '1') {
 
            if (firstOne == -1)
                firstOne = i;
 
            lastOne = i;
        }
    }
 
    if ((firstOne == -1) || (firstOne == lastOne)) {
        cout << 0;
        return;
    }
 
    // Count number of 0s present between
    // firstOne and lastOne
    for (int i = firstOne; i <= lastOne; i++) {
 
        if (str[i] == '0') {
 
            count++;
        }
    }
 
    // Print minimum operations
    cout << count << endl;
}
 
// Driver Code
int main()
{
 
    // Given string
    string str = "00110111011";
 
    countShifts(str);
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.util.*;
 
class GFG{
      
// Function to count indices substrings
// of 1s need to be shifted such that
// all 1s in the string are grouped together
static void countShifts(String str)
{
     
    // Stores first occurrence of '1'
    int firstOne = -1;
    
    // Stores last occurrence of '1'
    int lastOne = -1;
    
    // Count of 0s between firstOne and lastOne
    int count = 0;
     
    // Traverse the string to find the
    // first and last occurrences of '1'
    for(int i = 0; i < str.length(); i++)
    {
        if (str.charAt(i) == '1')
        {
            if (firstOne == -1)
                firstOne = i;
    
            lastOne = i;
        }
    }
    
    if ((firstOne == -1) || (firstOne == lastOne))
    {
        System.out.print(0);
        return;
    }
    
    // Count number of 0s present between
    // firstOne and lastOne
    for(int i = firstOne; i <= lastOne; i++)
    {
        if (str.charAt(i) == '0')
        {      
            count++;
        }
    }
    
    // Print minimum operations
    System.out.println(count);
}
 
// Driver code
public static void main (String[] args)
{
     
    // Given string
    String str = "00110111011";
    
    countShifts(str); 
}
}
 
// This code is contributed by code_hunt

# Python3 program for the above approach
  
# Function to count indices substrings
# of 1s need to be shifted such that
# all 1s in the string are grouped
# together
def countShifts(str):
     
    # Stores first occurrence of '1'
    firstOne = -1
  
    # Stores last occurrence of '1'
    lastOne = -1
  
    # Count of 0s between firstOne
    # and lastOne
    count = 0
  
    # Traverse the string to find the
    # first and last occurrences of '1'
    for i in range(len(str)):
        if (str[i] == '1'):
  
            if (firstOne == -1):
                firstOne = i
  
            lastOne = i
             
    if ((firstOne == -1) or
        (firstOne == lastOne)):
        print(0)
        return
     
    # Count number of 0s present between
    # firstOne and lastOne
    for i in range(firstOne, lastOne + 1, 1):
        if (str[i] == '0'):
            count += 1
             
    # Print minimum operations
    print(count)
 
# Driver Code
 
# Given string
str = "00110111011"
 
countShifts(str)
 
# This code is contributed by sanjoy_62

// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
     
    // Function to count indices substrings
    // of 1s need to be shifted such that
    // all 1s in the string are grouped together
    static void countShifts(string str)
    {
        // Stores first occurrence of '1'
        int firstOne = -1;
       
        // Stores last occurrence of '1'
        int lastOne = -1;
       
        // Count of 0s between firstOne and lastOne
        int count = 0;
       
        // Traverse the string to find the
        // first and last occurrences of '1'
        for (int i = 0; i < str.Length; i++)
        {
            if (str[i] == '1')
            {
       
                if (firstOne == -1)
                    firstOne = i;
       
                lastOne = i;
            }
        }
       
        if ((firstOne == -1) || (firstOne == lastOne))
        {
            Console.Write(0);
            return;
        }
       
        // Count number of 0s present between
        // firstOne and lastOne
        for (int i = firstOne; i <= lastOne; i++)
        {
       
            if (str[i] == '0')
            {      
                count++;
            }
        }
       
        // Print minimum operations
        Console.WriteLine(count);
    }
 
  // Driver code
  static void Main()
  {
     
        // Given string
        string str = "00110111011";
       
        countShifts(str); 
  }
}
 
// This code is contributed by divyeshrabadiya07

<script>
// javascript program to implement
// the above approach
 
    // Function to count indices substrings
    // of 1s need to be shifted such that
    // all 1s in the string are grouped together
    function countShifts(str)
    {
     
        // Stores first occurrence of '1'
        let firstOne = -1;
        
        // Stores last occurrence of '1'
        let lastOne = -1;
        
        // Count of 0s between firstOne and lastOne
        let count = 0;
        
        // Traverse the string to find the
        // first and last occurrences of '1'
        for (let i = 0; i < str.length; i++)
        {
            if (str[i] == '1')
            {
        
                if (firstOne == -1)
                    firstOne = i;
        
                lastOne = i;
            }
        }
        
        if ((firstOne == -1) || (firstOne == lastOne))
        {
            Console.Write(0);
            return;
        }
        
        // Count number of 0s present between
        // firstOne and lastOne
        for (let i = firstOne; i <= lastOne; i++)
        {
        
            if (str[i] == '0')
            {     
                count++;
            }
        }
        
        // Print minimum operations
        document.write(count);
    }
     
// Driver code
 
      // Given string
        let str = "00110111011";
        
        countShifts(str);
   
  // This code is contributed by splevel62.
</script>

2

Complejidad temporal: O(N)
Espacio auxiliar: O(1)