Dada una string S que consta solo de alfabetos ingleses en minúsculas, tenemos dos jugadores jugando el juego. Las reglas son las siguientes:
- El jugador puede eliminar cualquier carácter de la string S dada y escribirlo en papel en cualquier lado (izquierdo o derecho) de una string vacía.
- El jugador gana el juego, si en cualquier movimiento puede obtener primero una cuerda palindrómica de longitud > 1.
- Si no se puede formar una string palindrómica, el jugador 2 es declarado ganador.
Ambos juegan de manera óptima con el jugador 1 comenzando el juego. La tarea es encontrar al ganador del juego.
Ejemplos:
Entrada: S = “abc”
Salida: Jugador-2
Explicación:
Hay todos los caracteres únicos por lo que no
hay forma de formar una string palindrómica de longitud > 1Entrada: S = “abccab”
Salida: Jugador-2
Explicación:
Inicialmente, newString = “” está vacío.
Deje que el Jugador-1 elija el carácter ‘a’ y escríbalo en un papel.
Entonces, S = “bccab” y newString = “a”.
Ahora el jugador 2 elige el carácter ‘a’ de S y lo escribe en el lado izquierdo de newString.
Así, S = “bccb” y newString = “aa”.
Ahora, newString = “aa” es un palíndromo de longitud 2.
Por lo tanto, el Jugador-2 gana.
Enfoque: La idea es formular una condición en la que el jugador 1 siempre sea el ganador. Si la condición falla, el jugador 2 ganará el juego.
- Si solo hay un carácter único que aparece una vez en la string dada, y el resto de los caracteres aparecen más de 1, entonces el jugador 1 será el ganador, de lo contrario, el jugador 2 siempre ganará.
- Si tenemos todos los caracteres que aparecen más de una vez en la string dada, entonces el Jugador 2 siempre puede copiar el movimiento del Jugador 1 en su primer turno y gana.
- Además, si tenemos más de un carácter en la string que aparece una sola vez, nunca se puede formar una string palíndromo (en el caso óptimo). Por lo tanto, nuevamente, el Jugador-2 gana.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Implementation to find
// which player can form a palindromic
// string first in a game
#include <bits/stdc++.h>
using namespace std;
// Function to find
// winner of the game
int palindromeWinner(string& S)
{
// Array to Maintain frequency
// of the characters in S
int freq[26];
// Initialise freq array with 0
memset(freq, 0, sizeof freq);
// Maintain count of all
// distinct characters
int count = 0;
// Finding frequency of each character
for (int i = 0; i < (int)S.length();
++i) {
if (freq[S[i] - 'a'] == 0)
count++;
freq[S[i] - 'a']++;
}
// Count unique duplicate
// characters
int unique = 0;
int duplicate = 0;
// Loop to count the unique
// duplicate characters
for (int i = 0; i < 26; ++i) {
if (freq[i] == 1)
unique++;
else if (freq[i] >= 2)
duplicate++;
}
// Condition for Player-1
// to be winner
if (unique == 1 &&
(unique + duplicate) == count)
return 1;
// Else Player-2 is
// always winner
return 2;
}
// Driven Code
int main()
{
string S = "abcbc";
// Function call
cout << "Player-"
<< palindromeWinner(S)
<< endl;
return 0;
}
Java
// Java implementation to find which
// player can form a palindromic
// string first in a game
import java.util.*;
class GFG{
// Function to find
// winner of the game
static int palindromeWinner(String S)
{
// Array to maintain frequency
// of the characters in S
int freq[] = new int[26];
// Initialise freq array with 0
Arrays.fill(freq, 0);
// Maintain count of all
// distinct characters
int count = 0;
// Finding frequency of each character
for(int i = 0; i < (int)S.length(); ++i)
{
if (freq[S.charAt(i) - 'a'] == 0)
count++;
freq[S.charAt(i) - 'a']++;
}
// Count unique duplicate
// characters
int unique = 0;
int duplicate = 0;
// Loop to count the unique
// duplicate characters
for(int i = 0; i < 26; ++i)
{
if (freq[i] == 1)
unique++;
else if (freq[i] >= 2)
duplicate++;
}
// Condition for Player-1
// to be winner
if (unique == 1 &&
(unique + duplicate) == count)
return 1;
// Else Player-2 is
// always winner
return 2;
}
// Driver Code
public static void main(String s[])
{
String S = "abcbc";
// Function call
System.out.println("Player-" + palindromeWinner(S));
}
}
// This code is contributed by rutvik_56
Python3
# Python3 implementation to find
# which player can form a palindromic
# string first in a game
# Function to find
# winner of the game
def palindromeWinner(S):
# Array to Maintain frequency
# of the characters in S
# initialise freq array with 0
freq = [0 for i in range(0, 26)]
# Maintain count of all
# distinct characters
count = 0
# Finding frequency of each character
for i in range(0, len(S)):
if (freq[ord(S[i]) - 97] == 0):
count += 1
freq[ord(S[i]) - 97] += 1
# Count unique duplicate
# characters
unique = 0
duplicate = 0
# Loop to count the unique
# duplicate characters
for i in range(0, 26):
if (freq[i] == 1):
unique += 1
elif (freq[i] >= 2):
duplicate += 1
# Condition for Player-1
# to be winner
if (unique == 1 and
(unique + duplicate) == count):
return 1
# Else Player-2 is
# always winner
return 2
# Driven Code
S = "abcbc";
# Function call
print("Player-", palindromeWinner(S))
# This code is contributed by Sanjit_Prasad
C#
// C# implementation to find which
// player can form a palindromic
// string first in a game
using System;
class GFG{
// Function to find
// winner of the game
static int palindromeWinner(string S)
{
// Array to maintain frequency
// of the characters in S
int[] freq = new int[26];
// Maintain count of all
// distinct characters
int count = 0;
// Finding frequency of
// each character
for (int i = 0;
i < (int)S.Length; ++i)
{
if (freq[S[i] - 'a'] == 0)
count++;
freq[S[i] - 'a']++;
}
// Count unique duplicate
// characters
int unique = 0;
int duplicate = 0;
// Loop to count the unique
// duplicate characters
for (int i = 0; i < 26; ++i)
{
if (freq[i] == 1)
unique++;
else if (freq[i] >= 2)
duplicate++;
}
// Condition for Player-1
// to be winner
if (unique == 1 &&
(unique + duplicate) ==
count)
return 1;
// Else Player-2 is
// always winner
return 2;
}
// Driver Code
public static void Main(string[] s)
{
string S = "abcbc";
// Function call
Console.Write("Player-" +
palindromeWinner(S));
}
}
// This code is contributed by Chitranayal
Javascript
<script>
// Javascript implementation to find which
// player can form a palindromic
// string first in a game
// Function to find
// winner of the game
function palindromeWinner(S)
{
// Array to maintain frequency
// of the characters in S
let freq = new Array(26);
// Initialise freq array with 0
for(let i=0;i<26;i++)
{
freq[i]=0;
}
// Maintain count of all
// distinct characters
let count = 0;
// Finding frequency of each character
for(let i = 0; i < S.length; ++i)
{
if (freq[S[i].charCodeAt(0) - 'a'.charCodeAt(0)] == 0)
count++;
freq[S[i].charCodeAt(0) - 'a'.charCodeAt(0)]++;
}
// Count unique duplicate
// characters
let unique = 0;
let duplicate = 0;
// Loop to count the unique
// duplicate characters
for(let i = 0; i < 26; ++i)
{
if (freq[i] == 1)
unique++;
else if (freq[i] >= 2)
duplicate++;
}
// Condition for Player-1
// to be winner
if (unique == 1 &&
(unique + duplicate) == count)
return 1;
// Else Player-2 is
// always winner
return 2;
}
// Driver Code
let S = "abcbc";
// Function call
document.write("Player-" + palindromeWinner(S));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
Player-1
Complejidad de tiempo: O(N)
Publicación traducida automáticamente
Artículo escrito por Sanjit_Prasad y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA