Maximizar el número de cuerdas palindrómicas

Dadas N strings binarias b1, b2, b3…. mil millones La tarea es encontrar el número máximo de strings binarias que puede hacer palindrómicas intercambiando cualquier par de caracteres cualquier número de veces. Los caracteres pueden ser de la misma string o de strings diferentes
Ejemplos:
 

Input: N=3
1110
100110
010101
Output: 2
Explanation:
b1 = 1110
b2 = 100110 - > 110010
b3 = 010101 ->  110010
Now swap last 0 in s2 and s3
with 1's in s1
Final string become
b1 = 1000
b2 = 110011
b3 = 110011

where b1 and b2 are a palindrome

Input: N=3
1
1000
111110
Output: 3

Enfoque: 
Las longitudes de las cuerdas no cambian. También es importante observar que si se nos da una string binaria de longitud impar, siempre podemos intercambiar los caracteres de tal manera que la string se convierta en palindrómica. Esto se debe a que si la longitud es impar, entonces tendremos (números pares de ceros y un número impar de unos) o (número par de unos y un número impar de ceros). Por lo tanto, siempre se puede colocar de tal manera que esa cuerda sea palindrómica.
Ahora, como nuestra respuesta puede ser N o N-1. Tenemos que pensar en los casos en los que nuestra respuesta será N. Entonces, se nos dan N strings binarias. Si hay al menos 1 string de longitud impar, entonces nuestra respuesta seguramente será N. 
 

• Tome todos los 0 y 1 y quítelos de sus lugares. Entonces tendremos al menos un par de 0 o 1 y luego los colocaremos en sus lugares libres simétricamente (saltando los medios de longitud impar). Por ahora, todas las strings de longitud par están llenas y las strings de longitud impar tienen un espacio libre en el medio que se puede llenar fácilmente con los caracteres restantes. Entonces, en este caso, nuestra respuesta será N.
• Ahora, otro caso. Si tenemos todas las N strings de longitud par individualmente y el número total de 1 y 0 es par (es decir, el recuento total de 1 es par y el recuento total de 0 es par), entonces en este caso también nuestro ans será N. Esto se debe a que los 1 y 0 se pueden colocar simétricamente en todas las strings N para convertirlas en palíndromos. De lo contrario, nuestra respuesta será N-1.

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

// C++ program for the
// above approach
#include <bits/stdc++.h>
using namespace std;
 
int max_palindrome(string s[], int n)
{
    int flag = 0;
    for (int i = 0; i < n; i++) {
        // To check if there is
        // any string of odd length
        if (s[i].size() % 2 != 0) {
            flag = 1;
        }
    }
 
    // If there is at least
    // 1 string of odd
    // length.
    if (flag == 1) {
        return n;
    }
 
    int z = 0, o = 0;
 
    // If all the strings are
    // of even length.
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < s[i].size(); j++) {
            // Count of 0's in all
            // the strings
            if (s[i][j] == '0')
                z++;
            // Count of 1's in
            // all the strings
            else
                o++;
        }
    }
    // If z is even
    // and o is even
    // then ans will be N.
    if (o % 2 == 0 && z % 2 == 0) {
        return n;
    }
    // Otherwise ans will be N-1.
    else {
        return n - 1;
    }
}
 
// Driver code
int main()
{
    int n = 3;
    string s[n] = { "1110", "100110", "010101" };
    cout << max_palindrome(s, n);
 
    return 0;
}

// Java program for the above approach
class GFG
{
     
    static int max_palindrome(String []s, int n)
    {
        int flag = 0;
        for (int i = 0; i < n; i++)
        {
            // To check if there is
            // any string of odd length
            if (s[i].length() % 2 != 0)
            {
                flag = 1;
            }
        }
     
        // If there is at least
        // 1 string of odd
        // length.
        if (flag == 1)
        {
            return n;
        }
     
        int z = 0;
        int o = 0;
     
        // If all the strings are
        // of even length.
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < s[i].length(); j++)
            {
                // Count of 0's in all
                // the strings
                if (s[i].charAt(j) == '0')
                    z += 1;
                     
                // Count of 1's in
                // all the strings
                else
                    o += 1;
            }
        }
         
        // If z is even
        // and o is even
        // then ans will be N.
        if (o % 2 == 0 && z % 2 == 0)
        {
            return n;
        }
         
        // Otherwise ans will be N-1.
        else
        {
            return n - 1;
        }
    }
     
    // Driver code
    public static void main (String[] args)
    {
        int n = 3;
        String s[] = {"1110", "100110", "010101" };
        System.out.println(max_palindrome(s, n));
    }
}
 
// This code is contributed by AnkitRai01

# Python3 program for the above approach
def max_palindrome(s, n) :
 
    flag = 0;
    for i in range(n) :
         
        # To check if there is
        # any string of odd length
        if (len(s[i]) % 2 != 0) :
            flag = 1;
 
    # If there is at least
    # 1 string of odd
    # length.
    if (flag == 1) :
        return n;
 
    z = 0; o = 0;
 
    # If all the strings are
    # of even length.
    for i in range(n) :
        for j in range(len(s[i])) :
             
            # Count of 0's in all
            # the strings
            if (s[i][j] == '0') :
                z += 1;
                 
            # Count of 1's in
            # all the strings
            else :
                o += 1;
                 
    # If z is even
    # and o is even
    # then ans will be N.
    if (o % 2 == 0 and z % 2 == 0) :
        return n;
     
    # Otherwise ans will be N-1.
    else :
        return n - 1;
 
# Driver code
if __name__ == "__main__" :
 
    n = 3;
    s = [ "1110", "100110", "010101" ];
     
    print(max_palindrome(s, n));
 
# This code is contributed by AnkitRai01

// C# program for the above approach
using System;
 
class GFG
{
     
    static int max_palindrome(string []s, int n)
    {
        int flag = 0;
        for (int i = 0; i < n; i++)
        {
            // To check if there is
            // any string of odd length
            if (s[i].Length % 2 != 0)
            {
                flag = 1;
            }
        }
     
        // If there is at least
        // 1 string of odd
        // length.
        if (flag == 1)
        {
            return n;
        }
     
        int z = 0;
        int o = 0;
     
        // If all the strings are
        // of even length.
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < s[i].Length; j++)
            {
                // Count of 0's in all
                // the strings
                if (s[i][j] == '0')
                    z += 1;
                     
                // Count of 1's in
                // all the strings
                else
                    o += 1;
            }
        }
         
        // If z is even
        // and o is even
        // then ans will be N.
        if (o % 2 == 0 && z % 2 == 0)
        {
            return n;
        }
         
        // Otherwise ans will be N-1.
        else
        {
            return n - 1;
        }
    }
     
    // Driver code
    public static void Main ()
    {
        int n = 3;
        string []s = {"1110", "100110", "010101" };
        Console.WriteLine(max_palindrome(s, n));
    }
}
 
// This code is contributed by AnkitRai01

<script>
    // Javascript program for the above approach
     
    function max_palindrome(s, n)
    {
        let flag = 0;
        for (let i = 0; i < n; i++)
        {
            // To check if there is
            // any string of odd length
            if (s[i].length % 2 != 0)
            {
                flag = 1;
            }
        }
       
        // If there is at least
        // 1 string of odd
        // length.
        if (flag == 1)
        {
            return n;
        }
       
        let z = 0;
        let o = 0;
       
        // If all the strings are
        // of even length.
        for (let i = 0; i < n; i++)
        {
            for (let j = 0; j < s[i].length; j++)
            {
                // Count of 0's in all
                // the strings
                if (s[i][j] == '0')
                    z += 1;
                       
                // Count of 1's in
                // all the strings
                else
                    o += 1;
            }
        }
           
        // If z is even
        // and o is even
        // then ans will be N.
        if (o % 2 == 0 && z % 2 == 0)
        {
            return n;
        }
           
        // Otherwise ans will be N-1.
        else
        {
            return n - 1;
        }
    }
     
    let n = 3;
    let s = ["1110", "100110", "010101"];
    document.write(max_palindrome(s, n));
 
// This code is contributed by divyeshrabadiya07.
</script>

2

Complejidad de tiempo: O(n * |w|), donde w es la longitud máxima de la palabra en la string s

Espacio Auxiliar: O(1)