Encuentra al jugador que reorganiza los personajes para obtener primero una string de palíndromo

Dada una string S de longitud uniforme que consta solo de alfabetos ingleses en minúsculas, tenemos dos jugadores jugando el juego. Las reglas son las siguientes: 
 

• el jugador gana el juego si, en cualquier movimiento, un jugador puede reorganizar los caracteres de la string para obtener una string palíndromo.
• si el jugador no puede ganar el juego, debe eliminar cualquier carácter de la string.

Ambos jugadores juegan el juego de manera óptima con el jugador 1 comenzando el juego. La tarea es imprimir el ganador del juego. 
Ejemplos: 
 

Entrada: S = «abaaab» 
Salida: Jugador-1 El 
Jugador-1 en el primer paso organiza los personajes para obtener «aabbaa» y gana el juego. 
Entrada: S = «abca» 
Salida: Jugador-2 
Como el juego se desarrolla de manera óptima, el jugador-1 elimina ‘a’ para obtener la string «bca» que el jugador-2 no puede reorganizar en el segundo movimiento para ganar el juego. 
Player-2 elimina de manera óptima ‘b’ y la string ahora es «ca». 
En el tercer movimiento, el jugador 1 elimina «a» ya que no puede reorganizar los caracteres, la nueva string es «c», que el jugador 2 en el siguiente movimiento puede hacer un palíndromo. 
 

Acercarse: 
 

• Cuente las frecuencias de cada carácter en una array freq[].
• Cuente los caracteres que ocurren un número impar de veces.
• Si el conteo es 0 o un número impar , entonces el jugador 1 siempre ganará el juego; de lo contrario, el jugador 2 ganará porque el jugador 2 hará el último movimiento.

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

// C++ program to print the winner of the game
#include <bits/stdc++.h>
using namespace std;
 
// Function that returns the winner of the game
int returnWinner(string s, int l)
{
    // Initialize the freq array to 0
    int freq[26];
    memset(freq, 0, sizeof freq);
 
    // Iterate and count the frequencies
    // of each character in the string
    for (int i = 0; i < l; i++) {
        freq[s[i] - 'a']++;
    }
 
    int cnt = 0;
 
    // Count the odd occurring character
    for (int i = 0; i < 26; i++) {
 
        // If odd occurrence
        if (freq[i] & 1)
            cnt++;
    }
 
    // Check condition for Player-1 winning the game
    if (cnt == 0 || cnt & 1)
        return 1;
    else
        return 2;
}
 
// Driver code
int main()
{
    string s = "abaaab";
    int l = s.length();
 
    // Function call that returns the winner
    int winner = returnWinner(s, l);
 
    cout << "Player-" << winner;
    return 0;
}

// Java program to print the winner of the game
class GfG {
// Function that returns the winner of the game
static int returnWinner(String s, int l)
{
    // Initialize the freq array to 0
    int freq[]  =new int[26];
 
    // Iterate and count the frequencies
    // of each character in the string
    for (int i = 0; i < l; i++) {
        freq[s.charAt(i) - 'a']++;
    }
 
    int cnt = 0;
 
    // Count the odd occurring character
    for (int i = 0; i < 26; i++) {
 
        // If odd occurrence
        if (freq[i] % 2 != 0)
            cnt++;
    }
 
    // Check condition for Player-1 winning the game
    if ((cnt == 0)|| (cnt & 1) == 1)
        return 1;
    else
        return 2;
}
 
// Driver code
public static void main(String[] args)
{
    String s = "abaaab";
    int l = s.length();
 
    // Function call that returns the winner
    int winner = returnWinner(s, l);
 
    System.out.println("Player-" + winner);
}
}

# Python 3 program to print the winner of the game
 
# Function that returns the winner of the game
def returnWinner(s, l):
     
    # Initialize the freq array to 0
    freq = [0 for i in range(26)]
 
    # Iterate and count the frequencies
    # of each character in the string
    for i in range(0, l, 1):
        freq[ord(s[i]) - ord('a')] += 1
 
    cnt = 0
 
    # Count the odd occurring character
    for i in range(26):
         
        # If odd occurrence
        if (freq[i] % 2 != 0):
            cnt += 1
 
    # Check condition for Player-1
    # winning the game
    if (cnt == 0 or cnt & 1 == 1):
        return 1
    else:
        return 2
 
# Driver code
if __name__ == '__main__':
    s = "abaaab"
    l = len(s)
 
    # Function call that returns the winner
    winner = returnWinner(s, l)
 
    print("Player-", winner)
     
# This code is contributed by
# Surendra_Gangwar

// C# program to print the winner of the game
using System;
 
class GfG
{
     
// Function that returns the winner of the game
static int returnWinner(String s, int l)
{
    // Initialize the freq array to 0
    int []freq = new int[26];
 
    // Iterate and count the frequencies
    // of each character in the string
    for (int i = 0; i < l; i++)
    {
        freq[s[i] - 'a']++;
    }
 
    int cnt = 0;
 
    // Count the odd occurring character
    for (int i = 0; i < 26; i++)
    {
 
        // If odd occurrence
        if (freq[i] % 2 != 0)
            cnt++;
    }
 
    // Check condition for Player-1 winning the game
    if ((cnt == 0)|| (cnt & 1) == 1)
        return 1;
    else
        return 2;
}
 
// Driver code
public static void Main(String[] args)
{
    String s = "abaaab";
    int l = s.Length;
 
    // Function call that returns the winner
    int winner = returnWinner(s, l);
 
    Console.WriteLine("Player-" + winner);
}
}
 
// This code contributed by Rajput-Ji

<?php
// PHP program to print the winner
// of the game
 
// Function that returns the
// winner of the game
function returnWinner($s, $l)
{
    // Initialize the freq array to 0
    // int freq[26];
    // memset(freq, 0, sizeof freq);
    // $freg=array_fill()
    $freq = array_fill(0, 26, 0);
     
    // Iterate and count the frequencies
    // of each character in the string
    for ($i = 0; $i < $l; $i++)
    {
        $freq[$s[$i] - 'a']++;
    }
 
    $cnt = 0;
 
    // Count the odd occurring character
    for ($i = 0; $i < 26; $i++)
    {
 
        // If odd occurrence
        if ($freq[$i] & 1)
            $cnt++;
    }
 
    // Check condition for Player-1
    // winning the game
    if ($cnt == 0 || $cnt & 1)
        return 1;
    else
        return 2;
}
 
// Driver code
$s = "abaaab";
$l = strlen($s);
 
// Function call that returns
// the winner
$winner = returnWinner($s, $l);
 
echo "Player-" , $winner;
 
// This code is contributed
// by tushil
?>

<script>
    // Javascript program to print the winner of the game
     
    // Function that returns the winner of the game
    function returnWinner(s, l)
    {
        // Initialize the freq array to 0
        let freq = new Array(26);
        freq.fill(0);
 
        // Iterate and count the frequencies
        // of each character in the string
        for (let i = 0; i < l; i++)
        {
            freq[s[i].charCodeAt() - 'a'.charCodeAt()]++;
        }
 
        let cnt = 0;
 
        // Count the odd occurring character
        for (let i = 0; i < 26; i++)
        {
 
            // If odd occurrence
            if (freq[i] % 2 != 0)
                cnt++;
        }
 
        // Check condition for Player-1 winning the game
        if ((cnt == 0)|| (cnt & 1) == 1)
            return 1;
        else
            return 2;
    }
     
    let s = "abaaab";
    let l = s.length;
   
    // Function call that returns the winner
    let winner = returnWinner(s, l);
   
    document.write("Player-" + winner);
         
</script>

Player-1

Complejidad de tiempo: O(l), donde l es la longitud de la string. Como, estamos usando un bucle para atravesar l veces.

Espacio auxiliar: O(26), ya que estamos usando espacio adicional para almacenar las frecuencias.