Longitud de la substring más larga que se puede eliminar

Dada una string binaria (consta de solo 0 y 1). Si hay «100» como substring en la string, entonces podemos eliminar esta substring. ¿La tarea es encontrar la longitud de la substring más larga que se puede eliminar?

Ejemplos:  

Input  : str = "1011100000100"
Output : 6
// Sub-strings present in str that can be make removed 
// 101{110000}0{100}. First sub-string 110000-->100-->null,
// length is = 6. Second sub-string 100-->null, length is = 3

Input  : str = "111011"
Output : 0
// There is no sub-string which can be make null

Podemos resolver este problema usando un contenedor como vector en c++ o ArrayList en Java . A continuación se muestra el algoritmo para resolver este problema:  

• Tome un vector arr de tipo par. Cada elemento en arr almacena dos caracteres de valores y su índice respectivo en la string.
• Almacene pair(‘@’,-1) como base en arr. Tome la variable maxlen = 0 que almacena el resultado final.
• Ahora iterar uno por uno para todos los caracteres en la string, hacer un par de caracteres y su índice respectivo y almacenarlo en arr. En paralelo, también verifique la condición si después de insertar el i-ésimo carácter, los últimos tres elementos de ‘arr’ están formando una substring «100».
• Si existe una substring, elimínela de ‘arr’. Repita este ciclo varias veces hasta que obtenga la substring «100» en arr y anule el contenido eliminándolo continuamente.
• La diferencia de los índices del i-ésimo carácter y el índice del último elemento actualmente presente en arr después de la eliminación da la longitud de la substring que puede anularse mediante la eliminación continua de la substring «100», actualice maxlen.

Implementación:

// C++ implementation of program to find the maximum length
// that can be removed
#include<bits/stdc++.h>
using namespace std;
 
// Function to find the length of longest sub-string that
// can me make removed
// arr  --> pair type of array whose first field store
//          character in string and second field stores
//          corresponding index of that character
int longestNull(string str)
{
    vector<pair<char,int> > arr;
 
    // store {'@',-1} in arr , here this value will
    // work as base index
    arr.push_back({'@', -1});
 
    int maxlen = 0;   // Initialize result
 
    // one by one iterate characters of string
    for (int i = 0; i < str.length(); ++i)
    {
        // make pair of char and index , then store
        // them into arr
        arr.push_back({str[i], i});
 
        // now if last three elements of arr[]  are making
        // sub-string "100" or not
        while (arr.size()>=3 &&
               arr[arr.size()-3].first=='1' &&
               arr[arr.size()-2].first=='0' &&
               arr[arr.size()-1].first=='0')
        {
            // if above condition is true then delete
            // sub-string "100" from arr[]
            arr.pop_back();
            arr.pop_back();
            arr.pop_back();
        }
 
        // index of current last element in arr[]
        int tmp = arr.back().second;
 
        // This is important, here 'i' is the index of
        // current character inserted into arr[]
        // and 'tmp' is the index of last element in arr[]
        // after continuous deletion of sub-string
        // "100" from arr[] till we make it null, difference
        // of these to 'i-tmp' gives the length of current
        // sub-string that can be make null by continuous
        // deletion of sub-string "100"
        maxlen = max(maxlen, i - tmp);
    }
 
    return maxlen;
}
 
// Driver program to run the case
int main()
{
    cout << longestNull("1011100000100");
    return 0;
}

// Java implementation of program to find
// the maximum length that can be removed
import java.util.ArrayList;
 
public class GFG
{   
    // User defined class Pair
    static class Pair{
        char first;
        int second;
        Pair(char first, int second){
            this.first = first;
            this.second = second;
        }
    }
     
    /* Function to find the length of longest
    sub-string that can me make removed
     arr  --> pair type of array whose first
              field store character in string
              and second field stores
              corresponding index of that character*/
    static int longestNull(String str)
    {
        ArrayList<Pair> arr = new ArrayList<>();
      
        // store {'@',-1} in arr , here this value
        // will work as base index
        arr.add(new Pair('@', -1));
      
        int maxlen = 0;   // Initialize result
      
        // one by one iterate characters of string
        for (int i = 0; i < str.length(); ++i)
        {
            // make pair of char and index , then
            // store them into arr
            arr.add(new Pair(str.charAt(i), i));
      
            // now if last three elements of arr[]
            // are making sub-string "100" or not
            while (arr.size() >= 3 &&
                   arr.get(arr.size()-3).first=='1' &&
                   arr.get(arr.size()-2).first=='0' &&
                   arr.get(arr.size()-1).first=='0')
            {
                // if above condition is true then
                // delete sub-string "100" from arr[]
                arr.remove(arr.size() - 3);
                arr.remove(arr.size() - 2);
                arr.remove(arr.size() - 1);
            }
      
            // index of current last element in arr[]
            int tmp = arr.get(arr.size() - 1).second;
      
            // This is important, here 'i' is the index
            // of current character inserted into arr[]
            // and 'tmp' is the index of last element
            // in arr[] after continuous deletion of
            // sub-string "100" from arr[] till we make
            // it null, difference of these to 'i-tmp'
            // gives the length of current sub-string
            // that can be make null by continuous
            // deletion of sub-string "100"
            maxlen = Math.max(maxlen, i - tmp);
        }
      
        return maxlen;
    }
      
    // Driver program to run the case
    public static void main(String args[])
    {
        System.out.println(longestNull("1011100000100"));
    }
}
// This code is contributed by Sumit Ghosh

# Python3 implementation of program to find the maximum length
# that can be removed
 
# Function to find the length of longest sub-string that
# can me make removed
# arr --> pair type of array whose first field store
#         character in and second field stores
#         corresponding index of that character
def longestNull(S):
 
    arr=[]
 
    # store {'@',-1} in arr , here this value will
    # work as base index
    arr.append(['@', -1])
 
    maxlen = 0 # Initialize result
 
    # one by one iterate characters of String
    for i in range(len(S)):
        # make pair of char and index , then store
        # them into arr
        arr.append([S[i], i])
 
        # now if last three elements of arr[] are making
        # sub-string"100" or not
        while (len(arr)>=3 and
            arr[len(arr)-3][0]=='1' and
            arr[len(arr)-2][0]=='0' and
            arr[len(arr)-1][0]=='0'):
 
            # if above condition is true then delete
            # sub-string"100" from arr[]
            arr.pop()
            arr.pop()
            arr.pop()
 
        # index of current last element in arr[]
        tmp = arr[-1]
        # This is important, here 'i' is the index of
        # current character inserted into arr[]
        # and 'tmp' is the index of last element in arr[]
        # after continuous deletion of sub-String
        # "100" from arr[] till we make it null, difference
        # of these to 'i-tmp' gives the length of current
        # sub-string that can be make null by continuous
        # deletion of sub-string"100"
        maxlen = max(maxlen, i - tmp[1])
 
 
    return maxlen
 
 
# Driver code
 
print(longestNull("1011100000100"))
 
# This code is contributed by mohit kumar 29

// C# implementation of program to find
// the maximum length that can be removed
using System;
using System.Collections.Generic;
 
class GFG
{
    // User defined class Pair
    class Pair
    {
        public char first;
        public int second;
        public Pair(char first, int second)
        {
            this.first = first;
            this.second = second;
        }
    }
     
    /* Function to find the length of longest
    sub-string that can me make removed
    arr --> pair type of array whose first
            field store character in string
            and second field stores
            corresponding index of that character*/
    static int longestNull(String str)
    {
        List<Pair> arr = new List<Pair>();
     
        // store {'@',-1} in arr , here this value
        // will work as base index
        arr.Add(new Pair('@', -1));
     
        int maxlen = 0; // Initialize result
     
        // one by one iterate characters of string
        for (int i = 0; i < str.Length; ++i)
        {
            // make pair of char and index , then
            // store them into arr
            arr.Add(new Pair(str[i], i));
     
            // now if last three elements of []arr
            // are making sub-string "100" or not
            while (arr.Count >= 3 &&
                arr[arr.Count-3].first=='1' &&
                arr[arr.Count-2].first=='0' &&
                arr[arr.Count-1].first=='0')
            {
                // if above condition is true then
                // delete sub-string "100" from []arr
                arr.RemoveAt(arr.Count - 3);
                arr.RemoveAt(arr.Count - 2);
                arr.RemoveAt(arr.Count - 1);
            }
     
            // index of current last element in []arr
            int tmp = arr[arr.Count - 1].second;
     
            // This is important, here 'i' is the index
            // of current character inserted into []arr
            // and 'tmp' is the index of last element
            // in []arr after continuous deletion of
            // sub-string "100" from []arr till we make
            // it null, difference of these to 'i-tmp'
            // gives the length of current sub-string
            // that can be make null by continuous
            // deletion of sub-string "100"
            maxlen = Math.Max(maxlen, i - tmp);
        }
     
        return maxlen;
    }
     
    // Driver code
    public static void Main(String []args)
    {
        Console.WriteLine(longestNull("1011100000100"));
    }
}
 
// This code is contributed by PrinciRaj1992

<script>
// Javascript implementation of program to find
// the maximum length that can be removed
 
    /* Function to find the length of longest
    sub-string that can me make removed
     arr  --> pair type of array whose first
              field store character in string
              and second field stores
              corresponding index of that character*/
    function longestNull(str)
    {
        let arr = [];
        
        // store {'@',-1} in arr , here this value
        // will work as base index
        arr.push(['@', -1]);
        
        let maxlen = 0;   // Initialize result
        
        // one by one iterate characters of string
        for (let i = 0; i < str.length; ++i)
        {
            // make pair of char and index , then
            // store them into arr
            arr.push([str[i],i]);
        
            // now if last three elements of arr[]
            // are making sub-string "100" or not
            while (arr.length >= 3 &&
                   arr[arr.length-3][0]=='1' &&
                   arr[arr.length-2][0]=='0' &&
                   arr[arr.length-1][0]=='0')
            {
                // if above condition is true then
                // delete sub-string "100" from arr[]
                arr.pop();
                arr.pop();
                arr.pop();
            }
        
            // index of current last element in arr[]
            let tmp = arr[arr.length-1][1];
        
            // This is important, here 'i' is the index
            // of current character inserted into arr[]
            // and 'tmp' is the index of last element
            // in arr[] after continuous deletion of
            // sub-string "100" from arr[] till we make
            // it null, difference of these to 'i-tmp'
            // gives the length of current sub-string
            // that can be make null by continuous
            // deletion of sub-string "100"
            maxlen = Math.max(maxlen, i - tmp);
        }
        
        return maxlen;
    }
     
    // Driver program to run the case
    document.write(longestNull("1011100000100"));
 
     
    // This code is contributed by unknown2108
</script>

6

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

Este artículo es una contribución de Shashank Mishra (Gullu) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.