Given a string S consisting of lower-case English alphabets only, we have two players playing the game. The rules are as follows:
- The player can remove any character from the given string S and write it on paper on any side(left or right) of an empty string.
- The player wins the game, if at any move he can get a palindromic string first of length > 1.
- If a palindromic string cannot be formed, Player-2 is declared the winner.
Both play optimally with player-1 starting the game. The task is to find the winner of the game.
Examples:
Input: S = “abc”
Output: Player-2
Explanation:
There are all unique characters due to which there
is no way to form a palindromic string of length > 1Input: S = “abccab”
Output: Player-2
Explanation:
Initially, newString = “” is empty.
Let Player-1 choose character ‘a’ and write it on paper.
Then, S = “bccab” and newString = “a”.
Now Player-2 chooses character ‘a’ from S and writes it on the left side of newString.
Thus, S = “bccb” and newString = “aa”.
Now, newString = “aa” is a palindrome of length 2.
Hence, Player-2 wins.
Approach: The idea is to formulate a condition in which Player-1 is always going to be the winner. If the condition fails, then Player-2 will win the game.
- If there is only one unique character occurring once in the given string, and the rest of the characters occurring more than 1, then Player-1 is going to be the winner, else Player-2 will always win.
- If we have all characters that are occurring more than once in the given string, then Player-2 can always copy the Player-1 move in his first turn and wins.
- Also, if we have more than one character in the string occurring one time only, then a palindrome string can never be formed(in the optimal case). Hence, again, Player-2 wins.
Below is the implementation of the above approach:
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 gameint 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 Codeint 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 gameimport java.util.*;class GFG{ // Function to find // winner of the gamestatic 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 Codepublic 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 gameusing System;class GFG{// Function to find// winner of the gamestatic 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 Codepublic 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 gamefunction 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 Codelet S = "abcbc";// Function calldocument.write("Player-" + palindromeWinner(S));// This code is contributed by avanitrachhadiya2155</script> |
Output:
Player-1
Time Complexity: O(N), where N is the length of the given string.
Auxiliary Space: O(1), no extra space is required, so it is a constant.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
