Compruebe si la substring «10» aparece en la string binaria dada en todos los reemplazos posibles de ‘?’ con 1 o 0

Dada una string S que consta solo de ‘0’ , ‘1’ y ‘?’ , la tarea es verificar si existe una substring «10» en cada reemplazo posible del carácter ‘?’ con 1 o 0 .

Ejemplos:

Entrada: S = “1?0”
Salida: Sí
Explicación:
Los siguientes son todos los reemplazos posibles de ‘?’:

1. Reemplazo de la ‘?’ con 0 modifica la string a “100”. En la string de modificaciones, aparece la substring «10».
2. Reemplazo de la ‘?’ con 1 modifica la string a “110”. En la string de modificaciones, aparece la substring «10».

De todos los reemplazos posibles anteriores, la substring «10» aparece en todos los reemplazos, por lo tanto, escriba Sí.

Entrada: S= “??”
Salida: Sí

Enfoque: El problema dado se puede resolver utilizando un enfoque codicioso que se basa en la observación de que si la string S contiene muchos ‘?’ consecutivos , se puede reemplazar con un solo ‘?’ como en el peor de los casos, podemos reemplazarlo con todos 1 o 0 .

Por lo tanto, la idea es crear una nueva string a partir de la string S dada reemplazando el continuo ‘?’ con un solo ‘?’ y luego verifique si existe «10» o «1?0» como substring, entonces es posible obtener «10» como substring después de todos los reemplazos posibles, por lo tanto, imprima Sí . De lo contrario , imprima No.

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

// C++ Program to implement
// the above approach
#include <iostream>
using namespace std;
 
// Function to check it possible to get
// "10" as substring after all possible
// replacements
string check(string S, int n)
{
 
  // Initialize empty string ans
  string ans = "";
  int c = 0;
 
  // Run loop n times
  for (int i = 0; i < n; i++) {
 
    // If char is "?", then increment
    // c by 1
    if (S[i] == '?') {
      c++;
    }
    else {
 
      // Continuous '?' characters
      if (c) {
        ans += "?";
      }
      c = 0;
      ans += S[i];
    }
  }
 
  // Their is no consecutive "?"
  if (c) {
    ans += "?";
  }
 
  // Check if "10" or "1?0" exists
  // in the string ans or not
  if (ans.find("10") != -1 || ans.find("1?0") != -1) {
    return "Yes";
  }
  else {
    return "No";
  }
}
 
// Driver code
int main()
{
  string S = "1?0";
  int n = S.size();
  string ans = check(S, n);
  cout << ans;
  return 0;
}
// This code is contributed by parthmanchanda81

// Java program for the above approach
import java.io.*;
 
class GFG {
 
 
 // Returns true if s1 is substring of s2
    static int isSubstring(String s1, String s2)
    {
        int M = s1.length();
        int N = s2.length();
   
        /* A loop to slide pat[] one by one */
        for (int i = 0; i <= N - M; i++) {
            int j;
   
            /* For current index i, check for
            pattern match */
            for (j = 0; j < M; j++)
                if (s2.charAt(i + j) != s1.charAt(j))
                    break;
   
            if (j == M)
                return i;
        }
   
        return -1;
    }
   
  
// Function to check it possible to get
// "10" as substring after all possible
// replacements
static String check(String S, int n)
{
  
  // Initialize empty string ans
  String ans = "";
  int c = 0;
  
  // Run loop n times
  for (int i = 0; i < n; i++) {
  
    // If char is "?", then increment
    // c by 1
    if (S.charAt(i) == '?') {
      c++;
    }
    else {
  
      // Continuous '?' characters
      if (c != 0) {
        ans += "?";
      }
      c = 0;
      ans += S.charAt(i);
    }
  }
  
  // Their is no consecutive "?"
  if (c != 0) {
    ans += "?";
  }
  
  // Check if "10" or "1?0" exists
  // in the string ans or not
  if (isSubstring("10", S) != -1 || isSubstring("1?0", S) != -1) {
    return "Yes";
  }
  else {
    return "No";
  }
}
 
// Driver Code
public static void main (String[] args)
{
    String S = "1?0";
        int n = S.length();
        String ans = check(S, n);
        System.out.println(ans);
}
}
 
// This code is contributed by avijitmondal1998.

# Python program for the above approach
 
# Function to check it possible to get
# "10" as substring after all possible
# replacements
def check(S, n):
 
    # Initialize empty string ans
    ans = ""
    c = 0
 
    # Run loop n times
    for _ in range(n):
 
        # If char is "?", then increment
        # c by 1
        if S[_] == "?":
            c += 1
        else:
 
            # Continuous '?' characters
            if c:
                ans += "?"
 
            # Their is no consecutive "?"
            c = 0
            ans += S[_]
             
    # "?" still left
    if c:
        ans += "?"
 
    # Check if "10" or "1?0" exists
    # in the string ans or not
    if "10" in ans or "1?0" in ans:
        return "Yes"
    else:
        return "No"
 
 
# Driver Code
if __name__ == '__main__':
 
    S = "1?0"
    ans = check(S, len(S))
    print(ans)

// C# program for the approach
using System;
using System.Collections.Generic;
 
class GFG {
 
 // Returns true if s1 is substring of s2
    static int isSubstring(string s1, string s2)
    {
        int M = s1.Length;
        int N = s2.Length;
  
        /* A loop to slide pat[] one by one */
        for (int i = 0; i <= N - M; i++) {
            int j;
  
            /* For current index i, check for
            pattern match */
            for (j = 0; j < M; j++)
                if (s2[i + j] != s1[j])
                    break;
  
            if (j == M)
                return i;
        }
  
        return -1;
    }
  
 
// Function to check it possible to get
// "10" as substring after all possible
// replacements
static string check(string S, int n)
{
 
  // Initialize empty string ans
  string ans = "";
  int c = 0;
 
  // Run loop n times
  for (int i = 0; i < n; i++) {
 
    // If char is "?", then increment
    // c by 1
    if (S[i] == '?') {
      c++;
    }
    else {
 
      // Continuous '?' characters
      if (c != 0) {
        ans += "?";
      }
      c = 0;
      ans += S[i];
    }
  }
 
  // Their is no consecutive "?"
  if (c != 0) {
    ans += "?";
  }
 
  // Check if "10" or "1?0" exists
  // in the string ans or not
  if (isSubstring("10", S) != -1 || isSubstring("1?0", S) != -1) {
    return "Yes";
  }
  else {
    return "No";
  }
}
 
    // Driver Code
    public static void Main()
    {
        string S = "1?0";
        int n = S.Length;
        string ans = check(S, n);
        Console.Write(ans);
    }
}
 
// This code is contributed by sanjoy_62.

  <script>
        // JavaScript Program to implement
        // the above approach
 
        // Function to check it possible to get
        // "10" as substring after all possible
        // replacements
        function check(S, n) {
 
            // Initialize empty string ans
            ans = ""
            c = 0
 
            // Run loop n times
            for (let i = 0; i < n; i++) {
 
                // If char is "?", then increment
                // c by 1
                if (S[i] == "?")
                    c += 1
                else
 
                    // Continuous '?' characters
                    if (c != 0)
                        ans += "?"
 
                // Their is no consecutive "?"
                c = 0
                ans += S[i]
 
                // "?" still left
                if (c != 0)
                    ans += "?"
            }
             
            // Check if "10" or "1?0" exists
            // in the string ans or not
 
            if (ans.includes('10') || ans.includes('1?0'))
                return "Yes"
            else
                return "No"
 
        }
         
        // Driver Code
        S = "1?0"
        ans = check(S, S.length)
        document.write(ans)
 
// This code is contributed by Potta Lokesh
    </script>

Yes

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

Nota: El mismo enfoque se puede utilizar para las substrings “00”/”01″/”11″ también con cambios menores.