Given an even length string S consisting of lower-case English alphabets only, we have two players playing the game. The rules are as follows:
- the player wins the game, if, at any move, a player can re-arrange the characters of the string to get a palindrome string.
- if the player cannot win the game, he has to remove any character from the string.
Both players play the game optimally with player-1 starting the game. The task is to print the winner of the game.
Examples:
Input: S = “abaaab”
Output: Player-1
Player-1 in the first step arranges the characters to get “aabbaa” and wins the game.Input: S = “abca”
Output: Player-2
As the game is being played optimally, player-1 removes ‘a’ to get string “bca” which cannot be rearranged by player-2 in the second move to win the game.
Player-2 optimally removes ‘b’ and the string is now “ca”.
In the third move, player-1 removes “a” as he cannot rearrange the characters, the new string is “c”, which the player-2 at the next move can make a palindrome.
Approach:
- Count the frequencies of each character in a freq[] array.
- Count the characters that occur odd number of times.
- If the count is 0 or an odd number, then Player-1 will always win the game, else player-2 will win because player-2 will make the last move.
Below is the implementation of the above approach:
C++
// 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
// 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); } } |
Python3
# 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#
// 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 |
Javascript
<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> |
PHP
<?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 ?> |
Player-1
Complexity Analysis:
- Time Complexity: O(l), where l is the length of the string. As, we are using a loop to traverse l times.
- Auxiliary Space: O(26), as we are using extra space for storing the frequencies.
Using a set:
Approach:
In this approach, we will first create a set of all the characters in the string. Then, we will count the number of characters with odd frequency. If this count is greater than 1, Player-2 will win, otherwise, Player-1 will win.
Create a set of all the unique characters in the string s.
For each character c in the set, count the number of occurrences of c in s.
If the count of any character is odd, increment the odd_freq_count variable.
If odd_freq_count is greater than 1, return “Player-2”, indicating that Player-2 will win the game.
Otherwise, return “Player-1”, indicating that Player-1 will win the game.
C++
#include <bits/stdc++.h> #include <string> #include <unordered_set> std::string palindrome_game(std::string s) { std::unordered_set< char > chars; for ( char c : s) { chars.insert(c); } int odd_freq_count = 0; for ( char c : chars) { if (std::count(s.begin(), s.end(), c) % 2 != 0) { odd_freq_count++; } } if (odd_freq_count > 1) { return "Player-2" ; } else { return "Player-1" ; } } int main() { std::string s = "abaaab" ; std::string result = palindrome_game(s); std::cout << result << std::endl; return 0; } |
Java
import java.util.HashMap; import java.util.HashSet; public class Main { public static String palindromeGame(String s) { // Create a HashSet to store unique characters in the string. HashSet<Character> chars = new HashSet<>(); // Iterate through the string and add each character to the HashSet. for ( char c : s.toCharArray()) { chars.add(c); } int oddFreqCount = 0 ; for ( char c : chars) { // Count the frequency of each character in the string. int charCount = 0 ; for ( char ch : s.toCharArray()) { if (ch == c) { charCount++; } } // Check if the frequency is odd. if (charCount % 2 != 0 ) { oddFreqCount++; } } if (oddFreqCount > 1 ) { return "Player-2" ; } else { return "Player-1" ; } } public static void main(String[] args) { String s = "abaaab" ; String result = palindromeGame(s); System.out.println(result); } } // This code is contributed by akshitaguprzj3 |
Python3
def palindrome_game(s): chars = set (s) odd_freq_count = sum ( 1 for c in chars if s.count(c) % 2 ! = 0 ) if odd_freq_count > 1 : return "Player-2" else : return "Player-1" s = "abaaab" result = palindrome_game(s) print (result) # Output: Player-1 |
C#
using System; using System.Collections.Generic; class Program { // Function to determine the winner of the palindrome // game static string PalindromeGame( string s) { // Create a HashSet to store unique characters HashSet< char > chars = new HashSet< char >(); // Iterate through the string and insert characters // into the HashSet foreach ( char c in s) { chars.Add(c); } int oddFreqCount = 0; // Iterate through the unique characters in the // HashSet foreach ( char c in chars) { // Count the frequency of the character in the // original string int charFrequency = 0; foreach ( char originalChar in s) { if (originalChar == c) { charFrequency++; } } // Check if the character's frequency is odd if (charFrequency % 2 != 0) { oddFreqCount++; } } // Determine the winner based on odd frequency count if (oddFreqCount > 1) { return "Player-2" ; } else { return "Player-1" ; } } static void Main() { string s = "abaaab" ; string result = PalindromeGame(s); Console.WriteLine(result); Console.ReadKey(); } } |
Javascript
function palindrome_game(s) { // Create a set of characters in the string let chars = new Set(s); // Count the number of characters with odd frequency let odd_freq_count = 0; for (let c of chars) { if ((s.split(c).length - 1) % 2 != 0) { odd_freq_count++; } } // If there are more than one character with odd frequency, Player-2 wins if (odd_freq_count > 1) { return "Player-2" ; } else { return "Player-1" ; } } let s = "abaaab" ; let result = palindrome_game(s); console.log(result); |
Player-1
Time Complexity: O(n), where n is the length of the string
Auxiliary Space: O(k), where k is the number of unique characters in the string
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!