Recuento de posibles strings binarias distintas después de reemplazar «11» con «0»

Dada una string binaria str de tamaño N que contiene solo 0 y 1 , la tarea es contar todas las strings binarias distintas posibles cuando una substring «11» se puede reemplazar por «0».

Ejemplos:

Entrada: str = “11011”
Salida: 4
Explicación: Todas las combinaciones posibles son “11011”, “0011”, “1100”, “000”.

Entrada: str = “110011100011111”
Salida: 48

Enfoque ingenuo: la idea más simple para resolver el problema es intentar cambiar todas las substrings posibles y averiguar cuántas strings distintas se están formando en total.

Complejidad de Tiempo: O(2 ^N )
Espacio Auxiliar: O(2 ^N )

Enfoque eficiente: este problema se puede resolver de manera eficiente utilizando el concepto de programación dinámica con la ayuda de la siguiente idea:

• Considere que hay X número de grupos de 1s consecutivos. Averigüe de cuántas maneras se puede modificar cada uno de estos grupos cambiando «11» a «0». La multiplicación de todos esos valores será la respuesta requerida. 
• La programación dinámica (digamos array dp[]) se puede usar para encontrar las posibles combinaciones de 1s consecutivos. 
  • Si el i-ésimo elemento es 0, no se puede cambiar. Entonces dp[i] = 1. 
  • Si el i-ésimo carácter es 1, se puede mantener en 1 en las formas dp[i-1] o (i-1) el ésimo y el i-ésimo carácter se pueden reemplazar por 0 en las formas dp[i-2]. 
    Entonces dp[i] = dp[i-1]+dp[i-2] en este caso

Siga los pasos que se mencionan a continuación para resolver el problema:

• Iterar de i = 0 a N-1 y usar la observación anterior para llenar la array dp[].
• Nuevamente iterar desde el principio y multiplicar el número de combinaciones de los 1 consecutivos.
• Devuelve el valor multiplicado como la respuesta.

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

// C++ code to implement above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the
// total different combination
// possible
int total_count(string s, int n)
{
    int ans = 1, dp[n] = { 0 };
 
    // Base cases
    if (s[0] == '1')
        dp[0] = 1;
 
    if (s[1] == '1' && s[1] == s[0]) {
        dp[1] = 2;
    }
    else if (s[1] == '1') {
        dp[1] = 1;
    }
 
    // Iterating through every index
    // and storing the total
    // combination of string due to
    // all the adjacent 1's.
    for (int i = 2; i < n; i++) {
        if (s[i] == '1') {
            if (s[i] == s[i - 1]) {
                if (s[i - 1] == s[i - 2]) {
                    dp[i] = dp[i - 1]
                            + dp[i - 2];
                }
                else {
                    dp[i] = 2;
                }
            }
            else {
                dp[i] = 1;
            }
        }
    }
 
    // Total combinations possible
    // by multiplying all the individual
    // combinations.
    for (int i = 1; i < n; i++) {
        if (dp[i - 1] > dp[i]) {
            ans = ans * dp[i - 1];
        }
    }
    // Edge case
    if (dp[n - 1] != 0) {
        ans = ans * dp[n - 1];
    }
 
    // Returning the final value
    return ans;
}
 
// Driver code
int main()
{
    string str = "11011";
    int N;
    N = str.size();
 
    // Function call
    cout << total_count(str, N);
    return 0;
}

// JAVA code to implement above approach
import java.util.*;
class GFG
{
 
  // Function to return the
  // total different combination
  // possible
  public static int total_count(String s, int n)
  {
    int ans = 1;
    int dp[] = new int[n];
    for (int i = 0; i < n; ++i) {
      dp[i] = 0;
    }
 
    // Base cases
    if (s.charAt(0) == '1')
      dp[0] = 1;
 
    if (s.charAt(1) == '1'
        && s.charAt(1) == s.charAt(0)) {
      dp[1] = 2;
    }
    else if (s.charAt(1) == '1') {
      dp[1] = 1;
    }
 
    // Iterating through every index
    // and storing the total
    // combination of string due to
    // all the adjacent 1's.
    for (int i = 2; i < n; i++) {
      if (s.charAt(i) == '1') {
        if (s.charAt(i) == s.charAt(i - 1)) {
          if (s.charAt(i - 1)
              == s.charAt(i - 2)) {
            dp[i] = dp[i - 1] + dp[i - 2];
          }
          else {
            dp[i] = 2;
          }
        }
        else {
          dp[i] = 1;
        }
      }
    }
 
    // Total combinations possible
    // by multiplying all the individual
    // combinations.
    for (int i = 1; i < n; i++) {
      if (dp[i - 1] > dp[i]) {
        ans = ans * dp[i - 1];
      }
    }
    // Edge case
    if (dp[n - 1] != 0) {
      ans = ans * dp[n - 1];
    }
 
    // Returning the final value
    return ans;
  }
 
  // Driver code
  public static void main(String[] args)
  {
    String str = "11011";
    int N;
    N = str.length();
 
    // Function call
    System.out.print(total_count(str, N));
  }
}
 
// This code is contributed by Taranpreet

# Python3 code to implement the above approach
 
# function to return the total different
# combination possible
def total_count(s, n):
    ans = 1
    dp = [0] * n
 
    # base cases
    if s[0] == "1":
        dp[0] = 1
    if s[1] == "1" and s[1] == s[0]:
        dp[1] = 2
    elif s[1] == "1":
        dp[1] = 1
 
    # iterating through every index and storing
    # the total combination of strings due to all
    # the adjacent 1s
    for i in range(2, n):
        if s[i] == "1":
            if s[i] == s[i - 1]:
                if s[i - 1] == s[i - 2]:
                    dp[i] = dp[i - 1] + dp[i - 2]
                else:
                    dp[i] = 2
            else:
                dp[i] = 1
 
    # Total combinations possible by multiplying
    # all the individual combinations
    for i in range(1, n):
        if dp[i - 1] > dp[i]:
            ans *= dp[i - 1]
 
    # Edge case
    if dp[n - 1] != 0:
        ans *= dp[n - 1]
 
    # Returning the final value
    return ans
 
# Driver Code
string = "11011"
N = len(string)
 
# Function Call
print(total_count(string, N))
 
#This Code was contributed by phasing17

// C# code to implement above approach
using System;
 
public class GFG{
 
  // Function to return the
  // total different combination
  // possible
  static int total_count(string s, int n)
  {
    int ans = 1;
    int[] dp = new int[n];
    for (int i = 0; i < n; ++i) {
      dp[i] = 0;
    }
 
    // Base cases
    if (s[0] == '1')
      dp[0] = 1;
 
    if (s[1] == '1'
        && s[1] == s[0]) {
      dp[1] = 2;
    }
    else if (s[1] == '1') {
      dp[1] = 1;
    }
 
    // Iterating through every index
    // and storing the total
    // combination of string due to
    // all the adjacent 1's.
    for (int i = 2; i < n; i++) {
      if (s[i] == '1') {
        if (s[i] == s[i - 1]) {
          if (s[i - 1]
              == s[i - 2]) {
            dp[i] = dp[i - 1] + dp[i - 2];
          }
          else {
            dp[i] = 2;
          }
        }
        else {
          dp[i] = 1;
        }
      }
    }
 
    // Total combinations possible
    // by multiplying all the individual
    // combinations.
    for (int i = 1; i < n; i++) {
      if (dp[i - 1] > dp[i]) {
        ans = ans * dp[i - 1];
      }
    }
    // Edge case
    if (dp[n - 1] != 0) {
      ans = ans * dp[n - 1];
    }
 
    // Returning the final value
    return ans;
  }
 
  // Driver code
  static public void Main (){
 
    string str = "11011";
    int N;
    N = str.Length;
 
    // Function call
    Console.Write(total_count(str, N));
  }
}
 
// This code is contributed by hrithikgarg03188.

<script>
    // JavaScript code to implement above approach
 
    // Function to return the
    // total different combination
    // possible
    const total_count = (s, n) => {
        let ans = 1, dp = new Array(n).fill(0);
 
        // Base cases
        if (s[0] == '1')
            dp[0] = 1;
 
        if (s[1] == '1' && s[1] == s[0]) {
            dp[1] = 2;
        }
        else if (s[1] == '1') {
            dp[1] = 1;
        }
 
        // Iterating through every index
        // and storing the total
        // combination of string due to
        // all the adjacent 1's.
        for (let i = 2; i < n; i++) {
            if (s[i] == '1') {
                if (s[i] == s[i - 1]) {
                    if (s[i - 1] == s[i - 2]) {
                        dp[i] = dp[i - 1]
                            + dp[i - 2];
                    }
                    else {
                        dp[i] = 2;
                    }
                }
                else {
                    dp[i] = 1;
                }
            }
        }
 
        // Total combinations possible
        // by multiplying all the individual
        // combinations.
        for (let i = 1; i < n; i++) {
            if (dp[i - 1] > dp[i]) {
                ans = ans * dp[i - 1];
            }
        }
        // Edge case
        if (dp[n - 1] != 0) {
            ans = ans * dp[n - 1];
        }
 
        // Returning the final value
        return ans;
    }
 
    // Driver code
    let str = "11011";
    let N = str.length;
 
    // Function call
    document.write(total_count(str, N));
 
// This code is contributed by rakeshsahni
 
</script>

4

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