La substring más larga con como máximo X 0 e Y 1 de la string dada

Dada una string binaria S de longitud N , la tarea es encontrar la substring más larga con un número X de 0 como máximo y un número Y de 1 .

Ejemplo:

Entrada: S = «10101», N = 5, X = 1, Y = 2
Salida: 3
Explicación: La substring más larga con un máximo de 1 cero y 2 unos es «101» con una longitud de 3.

Entrada: S = «111», N = 3, X = 1, Y = 1
Salida: 1
Explicación: la substring más larga con como máximo 1 cero y 1 uno es «1» con longitud 1.

Entrada: S = “00000”, N = 5, X = 0, Y = 1
Salida: 0
Explicación: No existen substrings con un máximo de 0 números de ceros y 1 número de unos, ya que la string completa no contiene 1 en ninguna parte.

Enfoque ingenuo: el enfoque ingenuo para resolver este problema es encontrar todas las substrings y, para cada substring, contar el número de 0 y 1 en la substring y verificar si los conteos son como máximo X e Y respectivamente. 

Complejidad de Tiempo: O(N ² )
Espacio Auxiliar: O(1)

Enfoque eficiente: este problema se puede resolver utilizando el concepto de enfoque de dos punteros basado en la siguiente idea: 

Use dos punteros (i, j) , donde j es el último puntero e i es el puntero inicial. Use esos punteros para realizar un seguimiento de la cantidad de 0 y 1 en ese rango y actualícelos según el conteo de 0 y 1 en ese rango para ajustar la longitud de la substring. 

• Incremente el último puntero hasta que cualquiera de los recuentos de 0 y 1 no exceda su límite superior. 
• Si alguno de sus recuentos supera el límite proporcionado, incremente el primer puntero para disminuir el rango.
• El rango más largo dará la substring más larga.

Siga los pasos a continuación para resolver este problema.

• Inicialice i, j y maxLength a 0 .
• Atraviesa mientras j < N .
  • Cuente el número de 0 y 1 que termina en el j-ésimo índice.
  • Compruebe si el número de 0 y 1 satisface la condición dada.
  • En caso afirmativo, calcule el tamaño de la substring actual que comienza en i y termina en j .
    • Si el tamaño calculado es mayor que maxLength , actualice maxLength .
  • De lo contrario, reduzca el recuento de caracteres que se encuentra en el i-ésimo índice e incremente el valor de i .
• Devuelve maxLength como la respuesta final.

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

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the longest substring
// with at most X number of 0's
// and Y number of 1's
int longestKSubarray(string& S, int X, int Y)
{
    int N = S.length(), i = 0, j = 0;
    int count0 = 0, count1 = 0, maxLength = 0;
 
    while (j < N) {
 
        // Increment the count of jth character
        if (S[j] == '0') {
            count0++;
        }
        else {
            count1++;
        }
 
        // Check for Given condition
        if (count0 > X || count1 > Y) {
 
            // Reduce the count of ith character
            if (S[i] == '0') {
                count0--;
            }
            else {
                count1--;
            }
 
            // Move the ith pointer
            i++;
        }
 
        // Move the jth pointer
        j++;
 
        // Keep Updating the maxLength.
        maxLength = max(maxLength, j - i);
    }
    return maxLength;
}
 
// Driver's code
int main()
{
    string S = "10101";
    int X = 1, Y = 2;
 
    // Function call
    cout << longestKSubarray(S, X, Y);
    return 0;
}

// Java code to implement the approach
import java.io.*;
 
class GFG {
 
  // Function to find the longest substring
  // with at most X number of 0's
  // and Y number of 1's
  static int longestKSubarray(String S, int X, int Y)
  {
    int N = S.length(), i = 0, j = 0;
    int count0 = 0, count1 = 0, maxLength = 0;
 
    while (j < N) {
 
      // Increment the count of jth character
      if (S.charAt(j) == '0') {
        count0++;
      }
      else {
        count1++;
      }
 
      // Check for Given condition
      if (count0 > X || count1 > Y) {
 
        // Reduce the count of ith character
        if (S.charAt(i) == '0') {
          count0--;
        }
        else {
          count1--;
        }
 
        // Move the ith pointer
        i++;
      }
 
      // Move the jth pointer
      j++;
 
      // Keep Updating the maxLength.
      maxLength = Math.max(maxLength, j - i);
    }
    return maxLength;
  }
 
  // Driver's code
  public static void main (String[] args) {
 
    String S = "10101";
    int X = 1, Y = 2;
 
    // Function call
    System.out.print(longestKSubarray(S, X, Y));
  }
}
 
// This code is contributed by hrithikgarg03188.

# Python3 program to implement the above approach
 
# Function to find the longest substring
# with at most X number of 0's
# and Y number of 1's
def longestKSubarray(S, X, Y):
    N = len(S)
    i = 0
    j = 0
    count0 = 0
    count1 = 0
    maxLength = 0
    while j < N:
       
        # Increment the count of jth character
        if S[j] == "0":
            count0 += 1
        else:
            count1 += 1
 
        # Check for Given condition
        if count0 > X or count1 > Y:
           
            # Reduce the count of ith character
            if S[i] == "0":
                count0 -= 1
            else:
                count1 -= 1
                 
            # Move the ith pointer
            i += 1
             
        # Move the jth pointer
        j += 1
         
        # Keep Updating the maxLength.
        maxLength = max(maxLength, j - i)
    return maxLength
 
# Driver Code
S = "10101"
X = 1
Y = 2
 
# Function Call
print(longestKSubarray(S, X, Y))
 
# This code is contributed by phasing17

// C# code to implement the approach
using System;
class GFG {
 
  // Function to find the longest substring
  // with at most X number of 0's
  // and Y number of 1's
  static int longestKSubarray(string S, int X, int Y)
  {
    int N = S.Length, i = 0, j = 0;
    int count0 = 0, count1 = 0, maxLength = 0;
 
    while (j < N) {
 
      // Increment the count of jth character
      if (S[j] == '0') {
        count0++;
      }
      else {
        count1++;
      }
 
      // Check for Given condition
      if (count0 > X || count1 > Y) {
 
        // Reduce the count of ith character
        if (S[i] == '0') {
          count0--;
        }
        else {
          count1--;
        }
 
        // Move the ith pointer
        i++;
      }
 
      // Move the jth pointer
      j++;
 
      // Keep Updating the maxLength.
      maxLength = Math.Max(maxLength, j - i);
    }
    return maxLength;
  }
 
  // Driver's code
  public static void Main()
  {
 
    string S = "10101";
    int X = 1, Y = 2;
 
    // Function call
    Console.Write(longestKSubarray(S, X, Y));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
    // JavaScript code to implement the approach
 
 
    // Function to find the longest substring
    // with at most X number of 0's
    // and Y number of 1's
    const longestKSubarray = (S, X, Y) => {
        let N = S.length, i = 0, j = 0;
        let count0 = 0, count1 = 0, maxLength = 0;
 
        while (j < N) {
 
            // Increment the count of jth character
            if (S[j] == '0') {
                count0++;
            }
            else {
                count1++;
            }
 
            // Check for Given condition
            if (count0 > X || count1 > Y) {
 
                // Reduce the count of ith character
                if (S[i] == '0') {
                    count0--;
                }
                else {
                    count1--;
                }
 
                // Move the ith pointer
                i++;
            }
 
            // Move the jth pointer
            j++;
 
            // Keep Updating the maxLength.
            maxLength = Math.max(maxLength, j - i);
        }
        return maxLength;
    }
 
    // Driver's code
 
    let S = "10101";
    let X = 1, Y = 2;
 
    // Function call
    document.write(longestKSubarray(S, X, Y));
 
// This code is contributed by rakeshsahni
 
</script>

3

Complejidad del tiempo:O(N)
Espacio Auxiliar:O(1)