Two players A,B are playing a game. Player A has a string s with him, and player B has string t with him (of the same length and may consist of lowercase english letters only). Each player knows the string of the other player. Player A makes the first move and they keep alternating turns.
Players are building another string w which starts empty. In each move, a player removes any single character from his string and inserts this character at any position in w. If at any stage of the game, the string w is a palindrome and its length is greater than 1, then the player who made the last move wins. If both players strings are empty and w is not a palindrome then player B wins. Find out the winner assuming that both of them are playing optimally.
This problem is solved by breaking this game into few scenarios:
If all of first player’s letters are present into the second’s string, then the second player wins after his first move (the first player picks any letter and the second appends the same letter to w achieving a palindrome of length 2).
So the first player’s move must be a unique letter (not present in the second’s string). So his string must contain at least one unique letter. It’s obvious that the second player must choose a unique letter (not present in the first player’s string). Otherwise the first player would just choose the same letter the second player had chosen in his first move achieving a palindrome of length 3, and winning the game after his second move.
In case both of them had at least one unique letter, if the first player had a unique letter occurring at least twice, he would win easily. Picking this letter in his first and third move would result into a palindrome of length 3 (regardless of the second player’s move).
Any Other Scenario
If none of the above described scenarios is fulfilled, then player B would win for sure, that’s because there will be at least 2 unique letters in the string after the second move (and the first player’s letter) has no other copy (otherwise scenario 3 is fulfilled). And it’s clear that no palindrome can contain 2 unique letters. So the game is in second player’s control, he can just postpone placing the other copies (of his first played unique letter) or even place them arbitrarily so no palindrome is formed at any stage (Note that in some scenarios the second player may be able to form a palindrome but it doesn’t matter because he is the winner anyway). If no other copies exist then no palindrome ever