Recuento máximo de substrings de índice único 10 o 01 en una string binaria dada

Dada una string binaria str de longitud N , la tarea es contar el número máximo de pares adyacentes de forma «01» o «10» que se pueden formar a partir de la string binaria dada cuando se puede considerar un carácter para un solo par.

Nota: par adyacente significa par formado usando caracteres adyacentes.

Ejemplos:

Entrada: str = “0101110”
Salida: 3
Explicación: Los tres pares son “01” al principio primero,  
“01” comenzando en el segundo índice (indexación basada en 0)
y “10” al final de la string.
Observe que también se pueden formar 2 pares usando «10» del índice 1 y «10» al final.
Pero eso no da el número máximo de pares adyacentes.

Entrada: str = “0011”
Salida: 1

Entrada: str = “11”
Salida: 0

Enfoque: Este es un problema basado en la implementación. Siga los pasos mencionados aquí para resolver el problema:

• Atraviesa la cuerda de izquierda a derecha .
• Inicializa el conteo de pares con 0 y considera el carácter anterior como libre.
• Ejecute un ciclo desde 1 hasta el tamaño de la string .
• Compruebe si el carácter anterior es opuesto al carácter actual o no y también si es libre o no
  • En caso afirmativo , aumente el número de pares y establezca el carácter como no libre.
  • De lo contrario, continúe el recorrido en el bucle considerando el carácter como libre.
• Imprime el conteo de pares.

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

// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Count pairs function
void check_pairs(string str)
{
    // Initialize pairs with 0
    int pairs = 0;
 
    // Previous char is free to pair
    bool prev_c = true;
 
    // Traverse string from second position
    for (int i = 1; i < str.size(); i++) {
        // Check both char are opposite or not
        // and also check previous char
        // is free or not
        if (str[i] != str[i - 1] && prev_c) {
 
            // Once previous char paired
            // with other make it false
            prev_c = false;
 
            // Increment pairs count
            pairs++;
        }
        else {
 
            // Previous char is free for pair
            prev_c = true;
        }
    }
 
    // Print count of pairs of two characters
    cout << pairs;
}
 
// Driver Code
int main()
{
    string str = "0101110";
 
    // Function call
    check_pairs(str);
    return 0;
}

// Java code to implement the above approach
class GFG
{
 
  // Count pairs function
  static void check_pairs(String str)
  {
 
    // Initialize pairs with 0
    int pairs = 0;
 
    // Previous char is free to pair
    boolean prev_c = true;
 
    // Traverse String from second position
    for (int i = 1; i < str.length(); i++)
    {
 
      // Check both char are opposite or not
      // and also check previous char
      // is free or not
      if (str.charAt(i) != str.charAt(i - 1) && prev_c) {
 
        // Once previous char paired
        // with other make it false
        prev_c = false;
 
        // Increment pairs count
        pairs++;
      }
      else {
 
        // Previous char is free for pair
        prev_c = true;
      }
    }
 
    // Print count of pairs of two characters
    System.out.println(pairs);
  }
 
  // Driver Code
  public static void main(String args[])
  {
    String str = "0101110";
 
    // Function call
    check_pairs(str);
  }
}
 
// This code is contributed by gfgking

# python3 code to implement the above approach
 
# Count pairs function
def check_pairs(str):
 
    # Initialize pairs with 0
    pairs = 0
 
    # Previous char is free to pair
    prev_c = True
 
    # Traverse string from second position
    for i in range(1, len(str)):
       
        # Check both char are opposite or not
        # and also check previous char
        # is free or not
        if (str[i] != str[i - 1] and prev_c):
 
            # Once previous char paired
            # with other make it false
            prev_c = False
 
            # Increment pairs count
            pairs += 1
 
        else:
 
            # Previous char is free for pair
            prev_c = True
 
    # Print count of pairs of two characters
    print(pairs)
 
# Driver Code
if __name__ == "__main__":
 
    str = "0101110"
 
    # Function call
    check_pairs(str)
 
# This code is contributed by rakeshsahni

// C# code to implement the above approach
using System;
class GFG
{
 
  // Count pairs function
  static void check_pairs(string str)
  {
 
    // Initialize pairs with 0
    int pairs = 0;
 
    // Previous char is free to pair
    bool prev_c = true;
 
    // Traverse string from second position
    for (int i = 1; i < str.Length; i++)
    {
 
      // Check both char are opposite or not
      // and also check previous char
      // is free or not
      if (str[i] != str[i - 1] && prev_c) {
 
        // Once previous char paired
        // with other make it false
        prev_c = false;
 
        // Increment pairs count
        pairs++;
      }
      else {
 
        // Previous char is free for pair
        prev_c = true;
      }
    }
 
    // Print count of pairs of two characters
    Console.Write(pairs);
  }
 
  // Driver Code
  public static int Main()
  {
    string str = "0101110";
 
    // Function call
    check_pairs(str);
    return 0;
  }
}
 
// This code is contributed by Taranpreet

<script>
        // JavaScript code for the above approach
 
        // Count pairs function
        function check_pairs(str)
        {
         
            // Initialize pairs with 0
            let pairs = 0;
 
            // Previous char is free to pair
            let prev_c = true;
 
            // Traverse string from second position
            for (let i = 1; i < str.length; i++)
            {
             
                // Check both char are opposite or not
                // and also check previous char
                // is free or not
                if (str[i] != str[i - 1] && prev_c)
                {
 
                    // Once previous char paired
                    // with other make it false
                    prev_c = false;
 
                    // Increment pairs count
                    pairs++;
                }
                else {
 
                    // Previous char is free for pair
                    prev_c = true;
                }
            }
 
            // Print count of pairs of two characters
            document.write(pairs);
        }
 
        // Driver Code
        let str = "0101110";
 
        // Function call
        check_pairs(str);
 
       // This code is contributed by Potta Lokesh
    </script>

3

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