Reversiones mínimas de substring requeridas para hacer alternar la string binaria dada

Dada una string binaria S de longitud N , la tarea es contar el número mínimo de substrings de S que se requiere invertir para hacer que la string S se alterné. Si no es posible alternar strings, imprima “-1” .

Ejemplos:

Entrada: S = “10001110”
Salida: 2
Explicación:
En la primera operación, invertir la substring {S[3], .., S[6]} modifica la string a “10110010”.
En la segunda operación, invertir la substring {S[4], .. S[5]} modifica la string a «10101010», que es alterna.

Entrada: S = “100001”
Salida: -1
Explicación: No es posible obtener una string binaria alterna.

Enfoque: La idea se basa en la observación de que cuando se invierte una substring s[L, R] , entonces no más de dos pares s[L – 1] , s[L] y s[R] , S[R + 1 ] se modifican. Además, un par debe ser un par consecutivo de 00 y el otro 11 . Entonces, el número mínimo de operaciones se puede obtener emparejando 00 con 11 o con el borde izquierdo/derecho de S . Por lo tanto, el número requerido de operaciones es la mitad del número de pares consecutivos del mismo carácter. Siga los pasos a continuación para resolver el problema:

• Atraviese la string S para contar el número de 1 y 0 y almacenarlos en sum1 y sum0 respectivamente.
• Si la diferencia absoluta de sum1 y sum0 > 1 , imprima “-1” .
• De lo contrario, encuentre la cantidad de caracteres consecutivos que son iguales en la string S . Sea esa cuenta K para 1 y L para 0 .
• Después de completar los pasos anteriores, imprima el valor de K como resultado.

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 the minimum number
// of substrings required to be reversed
// to make the string S alternating
int minimumReverse(string s, int n)
{
    // Store count of consecutive pairs
    int k = 0 , l = 0 ;
 
    // Stores the count of 1s and 0s
    int sum1 = 0, sum0 = 0;
 
    // Traverse through the string
    for (int i = 1; i < n; i++) {
 
        if (s[i] == '1')
 
            // Increment 1s count
            sum1++;
        else
 
            // Increment 0s count
            sum0++;
 
        // Increment K if consecutive
        // same elements are found
        if (s[i] == s[i - 1]&& s[i] == '0')
            k++;
      else if( s[i] == s[i - 1]&& s[i] == '1')
        l++;
    }
   
    // Increment 1s count
    if(s[0]=='1')    
       sum1++;
    else  // Increment 0s count
       sum0++;
 
    // Check if it is possible or not
    if (abs(sum1 - sum0) > 1)
        return -1;
 
    // Otherwise, print the number
    // of required operations
    return max(k , l );
}
 
// Driver Code
int main()
{
    string S = "10001";
    int N = S.size();
 
    // Function Call
    cout << minimumReverse(S, N);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
import java.lang.*;
 
class GFG
{
 
  // Function to count the minimum number
  // of substrings required to be reversed
  // to make the string S alternating
  static int minimumReverse(String s, int n)
  {
 
    // Store count of consecutive pairs
    int k = 0 , l = 0 ;
 
    // Stores the count of 1s and 0s
    int sum1 = 0, sum0 = 0;
 
    // Traverse through the string
    for (int i = 1; i < n; i++)
    {
 
      if (s.charAt(i) == '1')
 
        // Increment 1s count
        sum1++;
      else
 
        // Increment 0s count
        sum0++;
 
      // Increment K if consecutive
      // same elements are found
      if (s.charAt(i) == s.charAt(i - 1) && s.charAt(i) == '0')
        k++;
      else if( s.charAt(i) == s.charAt(i - 1) && s.charAt(i) == '1')
        l++;
    }
 
    // Increment 1s count
    if(s.charAt(0)=='1')    
      sum1++;
    else  // Increment 0s count
      sum0++;
 
    // Check if it is possible or not
    if (Math.abs(sum1 - sum0) > 1)
      return -1;
 
    // Otherwise, print the number
    // of required operations
    return Math.max(k , l);
  }
 
  // Driver code
  public static void main (String[] args)
  {
    String S = "10001";
    int N = S.length();
 
    // Function Call
    System.out.print(minimumReverse(S, N));
 
  }
}
 
// This code is contributed by offbeat

# Python program for the above approach
 
# Function to count the minimum number
# of substrings required to be reversed
# to make the string S alternating
def minimumReverse(s, n):
   
    # Store count of consecutive pairs
    k = 0;
    l = 0;
 
    # Stores the count of 1s and 0s
    sum1 = 0;
    sum0 = 0;
 
    # Traverse through the string
    for i in range(1, n):
        if (s[i] == '1'):
 
            # Increment 1s count
            sum1 += 1;
        else:
 
            # Increment 0s count
            sum0 += 1;
 
        # Increment K if consecutive
        # same elements are found
        if (s[i] == s[i - 1] and s[i] == '0'):
            k += 1;
        elif (s[i] == s[i - 1] and s[i] == '1'):
            l += 1;
 
    # Increment 1s count
    if (s[0] == '1'):
        sum1 += 1;
    else:  # Increment 0s count
        sum0 += 1;
 
    # Check if it is possible or not
    if (abs(sum1 - sum0) > 1):
        return -1;
 
    # Otherwise, print the number
    # of required operations
    return max(k, l);
 
# Driver code
if __name__ == '__main__':
    S = "10001";
    N = len(S);
 
    # Function Call
    print(minimumReverse(S, N));
 
# This code is contributed by shikhasingrajput

// C# program for the above approach
using System;
 
public class GFG
{
 
  // Function to count the minimum number
  // of substrings required to be reversed
  // to make the string S alternating
  static int minimumReverse(String s, int n)
  {
 
    // Store count of consecutive pairs
    int k = 0 , l = 0 ;
 
    // Stores the count of 1s and 0s
    int sum1 = 0, sum0 = 0;
 
    // Traverse through the string
    for (int i = 1; i < n; i++)
    {
 
      if (s[i] == '1')
 
        // Increment 1s count
        sum1++;
      else
 
        // Increment 0s count
        sum0++;
 
      // Increment K if consecutive
      // same elements are found
      if (s[i] == s[i-1] && s[i] == '0')
        k++;
      else if( s[i] == s[i-1] && s[i] == '1')
        l++;
    }
 
    // Increment 1s count
    if(s[0] == '1')    
      sum1++;
    else  // Increment 0s count
      sum0++;
 
    // Check if it is possible or not
    if (Math.Abs(sum1 - sum0) > 1)
      return -1;
 
    // Otherwise, print the number
    // of required operations
    return Math.Max(k , l);
  }
 
  // Driver code
  public static void Main(String[] args)
  {
    String S = "10001";
    int N = S.Length;
 
    // Function Call
    Console.Write(minimumReverse(S, N));
  }
}
 
 
// This code is contributed by shikhasingrajput

<script>
 
// JavaScript program to implement
// the above approach
 
  // Function to count the minimum number
  // of substrings required to be reversed
  // to make the string S alternating
  function minimumReverse(s, n)
  {
  
    // Store count of consecutive pairs
    let k = 0 , l = 0 ;
  
    // Stores the count of 1s and 0s
    let sum1 = 0, sum0 = 0;
  
    // Traverse through the string
    for (let i = 1; i < n; i++)
    {
  
      if (s[i] == '1')
  
        // Increment 1s count
        sum1++;
      else
  
        // Increment 0s count
        sum0++;
  
      // Increment K if consecutive
      // same elements are found
      if (s[i] == s[i-1] && s[i] == '0')
        k++;
      else if( s[i] == s[i-1] && s[i] == '1')
        l++;
    }
  
    // Increment 1s count
    if(s[0] == '1')   
      sum1++;
    else  // Increment 0s count
      sum0++;
  
    // Check if it is possible or not
    if (Math.abs(sum1 - sum0) > 1)
      return -1;
  
    // Otherwise, print the number
    // of required operations
    return Math.max(k , l);
  }
      
// Driver code
         
    let S = "10001";
    let N = S.length;
  
    // Function Call
    document.write(minimumReverse(S, N));
 
</script>

2

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