La substring más grande de una string binaria divisible por 2

Dada la string binaria str de longitud N , la tarea es encontrar la substring más larga divisible por 2 . Si no existe tal substring, imprima -1 .

Ejemplos:  

Entrada: str = “11100011” 
Salida: 111000  La substring
más grande divisible por 2 es “111000”.
Entrada: str = «1111» 
Salida: -1 
No hay ninguna substring de la string dada 
que sea divisible por 2.  

Enfoque ingenuo: un enfoque ingenuo será generar todas esas substrings y comprobar si son divisibles por 2. La complejidad temporal de este enfoque será O(N ³ ).

Mejor enfoque: un enfoque sencillo será eliminar caracteres del final de la string mientras el último carácter es 1 . En el momento en que se encuentra un 0 , la string actual será divisible por 2 ya que termina en 0 . La complejidad temporal de este enfoque será O(N).

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

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the largest
// substring divisible by 2
string largestSubStr(string s)
{
    // While the last character of
    // the string is '1', pop it
    while (s.size() and s[s.size() - 1] == '1')
        s.pop_back();
 
    // If the original string had no '0'
    if (s.size() == 0)
        return "-1";
    else
        return s;
}
 
// Driver code
int main()
{
    string s = "11001";
 
    cout << largestSubStr(s);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
     
    // Function to return the largest
    // substring divisible by 2
    static String largestSubStr(String s)
    {
        // While the last character of
        // the string is '1', pop it
        while (s.length() != 0 &&
               s.charAt(s.length() - 1) == '1')
            s = s.substring(0, s.length() - 1);
     
        // If the original string had no '0'
        if (s.length() == 0)
            return "-1";
        else
            return s;
    }
     
    // Driver code
    public static void main (String[] args)
    {
        String s = "11001";
     
        System.out.println(largestSubStr(s));
    }
}
 
// This code is contributed by AnkitRai01

# Python3 implementation of the approach
 
# Function to return the largest
# substring divisible by 2
def largestSubStr(s) :
 
    # While the last character of
    # the string is '1', pop it
    while (len(s) and s[len(s) - 1] == '1') :
        s = s[:len(s) - 1];
 
    # If the original string had no '0'
    if (len(s) == 0) :
        return "-1";
    else :
        return s;
 
# Driver code
if __name__ == "__main__" :
 
    s = "11001";
 
    print(largestSubStr(s));
 
# This code is contributed by AnkitRai01

// C# implementation of the approach
using System;
 
class GFG
{
     
    // Function to return the largest
    // substring divisible by 2
    static string largestSubStr(string s)
    {
        // While the last character of
        // the string is '1', pop it
        while (s.Length != 0 &&
               s[s.Length - 1] == '1')
            s = s.Substring(0, s.Length - 1);
     
        // If the original string had no '0'
        if (s.Length == 0)
            return "-1";
        else
            return s;
    }
     
    // Driver code
    public static void Main ()
    {
        string s = "11001";
     
        Console.WriteLine(largestSubStr(s));
    }
}
 
// This code is contributed by AnkitRai01

<script>
 
// Javascript implementation of the approach
 
// Function to return the largest
// substring divisible by 2
function largestSubStr(s)
{
    // While the last character of
    // the string is '1', pop it
    while (s.length && s[s.length - 1] == '1')
        s = s.substring(0,s.length-1);;
 
    // If the original string had no '0'
    if (s.length == 0)
        return "-1";
    else
        return s;
}
 
// Driver code
var s = "11001";
document.write( largestSubStr(s));
 
</script>

1100