Prerequisite :
Nim’s game
Difficulty :
Easy
Problem statement :
You are given a string in which in each turn you have to remove a subset of alphabets from
the string where all letters in the subset must be same. You have to find at which turn you cannot make further moves.
Explanations :
The problem can be reduced to a Nim’s game. We can create 26 piles of alphabets. First pile
will contain all the ‘a’ in the input string, second pile will contain all ‘b’ and so on. So the problem reduces to choose a pile in a single turn, remove some alphabets from the pile (at least 1 and at most all). Keep doing it till all piles become empty.
This is a standard Nim’s game and solution is to xor the number of elements in each pile. If
the result is 0, the player who made the first turn looses, else wins.
Reference: