Encuentra la substring de paridad impar de longitud máxima

Dada una string binaria str , la tarea es encontrar la longitud máxima de la substring de str que tiene paridad impar. Se dice que una string binaria es de paridad impar si contiene un número impar de 1 s.

Ejemplos: 

Entrada: str = “1001110” 
Salida: 6 
“001110” es la substring válida.

Entrada: str = «101101» 
Salida: 5 
 

Acercarse:  

1. Cuente el número de 1 s en la string dada y guárdelo en una variable cnt .
2. Si cnt = 0 , entonces no es posible una substring con paridad impar, por lo que el resultado será 0 .
3. Si cnt es impar , el resultado será la string completa.
4. Ahora, en el caso de que cnt sea par y > 0 , la substring requerida comenzará en el índice 0 y terminará justo antes de la última aparición de 1 o comenzará justo después de la primera aparición de 1 y terminará al final de la string dada. .
5. Elige la de mayor longitud entre las dos substrings del paso anterior.

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

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
    // finds the index of character of string
    int indexOf(string s, char c, int i)
    {
        for(; i < s.length(); i++)
        if(s[i] == c)
        return i;
         
        return -1;
    }
     
    // finds the last index of character of string
    int lastIndexOf(string s,char c,int i)
    {
        for(; i >= 0; i--)
        if(s[i] == c)
            return i;
         
        return -1;
    }
 
    // Function to return the maximum
    // length of the sub-string which
    // contains odd number of 1s
    int maxOddParity(string str, int n)
    {
 
        // Find the count of 1s in
        // the given string
        int cnt = 0;
        for (int i = 0; i < n; i++)
            if (str[i] == '1')
                cnt++;
 
        // If there are only 0s in the string
        if (cnt == 0)
            return 0;
 
        // If the count of 1s is odd then
        // the complete string has odd parity
        if (cnt % 2 == 1)
            return n;
 
        // Index of the first and the second
        // occurrences of '1' in the string
        int firstOcc = indexOf(str,'1',0);
        int secondOcc = indexOf(str,'1', firstOcc + 1);
 
        // Index of the last and the second last
        // occurrences of '1' in the string
        int lastOcc = lastIndexOf(str,'1',str.length()-1);
        int secondLastOcc = lastIndexOf(str,'1', lastOcc - 1);
 
        // Result will the sub-string ending just
        // before the last occurrence of '1' or the
        // sub-string starting just after the first
        // occurrence of '1'
        // choose the one with the maximum length
        return max(lastOcc, n - firstOcc - 1);
    }
 
    // Driver code
    int main()
    {
        string str = "101101";
        int n = str.length();
        cout<<(maxOddParity(str, n));
    }
 
// This code is contributed by Arnab Kundu

// Java implementation of the approach
public class GFG {
 
    // Function to return the maximum
    // length of the sub-string which
    // contains odd number of 1s
    static int maxOddParity(String str, int n)
    {
 
        // Find the count of 1s in
        // the given string
        int cnt = 0;
        for (int i = 0; i < n; i++)
            if (str.charAt(i) == '1')
                cnt++;
 
        // If there are only 0s in the string
        if (cnt == 0)
            return 0;
 
        // If the count of 1s is odd then
        // the complete string has odd parity
        if (cnt % 2 == 1)
            return n;
 
        // Index of the first and the second
        // occurrences of '1' in the string
        int firstOcc = str.indexOf('1');
        int secondOcc = str.indexOf('1', firstOcc + 1);
 
        // Index of the last and the second last
        // occurrences of '1' in the string
        int lastOcc = str.lastIndexOf('1');
        int secondLastOcc = str.lastIndexOf('1', lastOcc - 1);
 
        // Result will the sub-string ending just
        // before the last occurrence of '1' or the
        // sub-string starting just after the first
        // occurrence of '1'
        // choose the one with the maximum length
        return Math.max(lastOcc, n - firstOcc - 1);
    }
 
    // Driver code
    public static void main(String[] args)
    {
        String str = "101101";
        int n = str.length();
        System.out.print(maxOddParity(str, n));
    }
}

# Python3 implementation of the approach
 
# Function to return the maximum
# length of the sub-string which
# contains odd number of 1s
def maxOddParity(string, n):
 
    # Find the count of 1s in
    # the given string
    cnt = 0
    for i in range(n):
        if string[i] != '1':
            cnt += 1
 
    # If there are only 0s in the string
    if cnt == 0:
        return 0
 
    # If the count of 1s is odd then
    # the complete string has odd parity
    if cnt % 2 == 1:
        return n
 
    # Index of the first and the second
    # occurrences of '1' in the string
    firstOcc = string.index('1')
    secondOcc = string.index('1', firstOcc + 1)
 
    # Index of the last and the second last
    # occurrences of '1' in the string
    lastOcc = string.rindex('1')
    secondLastOcc = string.rindex('1', 0, lastOcc)
 
    # Result will the sub-string ending just
    # before the last occurrence of '1' or the
    # sub-string starting just after the first
    # occurrence of '1'
    # choose the one with the maximum length
    return max(lastOcc, n - firstOcc - 1)
 
# Driver Code
if __name__ == "__main__":
    string = "101101"
    n = len(string)
    print(maxOddParity(string, n))
 
# This code is contributed by
# sanjeev2552

// C# implementation of the above approach
using System;
 
class GFG
{
 
    // Function to return the maximum
    // length of the sub-string which
    // contains odd number of 1s
    static int maxOddParity(String str, int n)
    {
 
        // Find the count of 1s in
        // the given string
        int cnt = 0;
        for (int i = 0; i < n; i++)
            if (str[i] == '1')
                cnt++;
 
        // If there are only 0s in the string
        if (cnt == 0)
            return 0;
 
        // If the count of 1s is odd then
        // the complete string has odd parity
        if (cnt % 2 == 1)
            return n;
 
        // Index of the first and the second
        // occurrences of '1' in the string
        int firstOcc = str.IndexOf('1');
        int secondOcc = str.IndexOf('1', firstOcc + 1);
 
        // Index of the last and the second last
        // occurrences of '1' in the string
        int lastOcc = str.LastIndexOf('1');
        int secondLastOcc = str.LastIndexOf('1', lastOcc - 1);
 
        // Result will the sub-string ending just
        // before the last occurrence of '1' or the
        // sub-string starting just after the first
        // occurrence of '1'
        // choose the one with the maximum length
        return Math.Max(lastOcc, n - firstOcc - 1);
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        String str = "101101";
        int n = str.Length;
        Console.WriteLine(maxOddParity(str, n));
    }
}
 
/* This code contributed by PrinciRaj1992 */

<script>
 
// Javascript implementation of the above approach
 
// Function to return the maximum
// length of the sub-string which
// contains odd number of 1s
function maxOddParity(str, n)
{
     
    // Find the count of 1s in
    // the given string
    var cnt = 0;
    for(var i = 0; i < n; i++)
        if (str[i] == '1')
            cnt++;
 
    // If there are only 0s in the string
    if (cnt == 0)
        return 0;
 
    // If the count of 1s is odd then
    // the complete string has odd parity
    if (cnt % 2 == 1)
        return n;
 
    // Index of the first and the second
    // occurrences of '1' in the string
    var firstOcc = str.indexOf('1');
    var secondOcc = str.indexOf(
        '1', firstOcc + 1);
 
    // Index of the last and the second last
    // occurrences of '1' in the string
    var lastOcc = str.lastIndexOf('1');
    var secondLastOcc = str.lastIndexOf(
        '1', lastOcc - 1);
 
    // Result will the sub-string ending just
    // before the last occurrence of '1' or the
    // sub-string starting just after the first
    // occurrence of '1'
    // choose the one with the maximum length
    return Math.max(lastOcc, n - firstOcc - 1);
}
 
// Driver code
var str = "101101";
var n = str.length;
 
document.write(maxOddParity(str, n));
 
// This code is contributed by bunnyram19
 
</script>

5