Palindromic String Game

Question

There are two players $A$, $B$ playing a game. Player $A$ has a string $s$ with him, and player $B$ has string $t$ with him. Both $s$ and $t$ consist only of lower case English letters and are of equal length. $A$ makes the first move, then $B$, then $A$, and so on alternatively. Before the start of the game, the players know the content of both the strings $s$ and $t$.

These players are building one other string $w$ during the game. Initially, the string $w$ is empty. In each move, a player removes any one character from their respective string and adds this character anywhere (at any position) in the string $w$. If at any stage of the game, the string $w$ is of length greater than $1$ and is a palindrome, then the player who made the last move wins.

If even after the game finishes (ie. when both $s$ and $t$ have become empty strings), no one is able to make the string w a palindrome, then player $B$ wins.

My Strategy
If any character ($a-z$) is having a frequency greater than $1$ in string $s$ and it's not present in $t$ so $A$ will win other wise $B$.

Is my approach is correct ? Or is there any other way for $A$ to win ?

Answer 1

I am not sure if i am right but this is my strategy:
If lets assume the characters in string s as a set A and characters in string t as a set B.

1.If B is a subset of A then A will win
Eg: aabbe ab
A ={a,b,e} B={a,b}
Player A will use e at first and then B is forced to use one of characters that A has so A can match it and win.

2.If A is a subset of B then B will win
Eg:aabb aabbe
This is pretty obvious because whatever A uses B matches it and wins the game

3.If A and B are equal then B will win Eg: aabbcc aabbc
Whatever A uses is matched by B and hence B wins.

4.If A has 2 or more of the same characters that B doesn't have then A will win.
Eg:aabbc cbbe
A will use a at first.
Since B doesn't have a it will try to use one of the other characters and A will match again to form a palindrome.

5.If A and B are not subsets of each other,then B wins: s=aabcdef t=abcdgh
A={a,b,c,d,e,f} t={a,b,c,d,g,h}
Obviously A will try to use a character that B doesn't have(e or f),B will also use a character that A doesn't have(g or h).I think in the end B will try to make sure that A doesn't form a palindrome and there by winning.

Not sure it is right tho.

Answer 2

Credit: Anantha proposed a solution without a complete proof. I am just providing the proof that the solution is indeed correct.

We let the characters in string $s$ as a set $S_A$ and characters in string $t$ as a set $S_B$.

Claim: If $S_B \subsetneq S_A$ or if player $A$ contains at least $2$ letters that $B$ does not have , then player $A$ wins. Otherwise player $B$ wins.

Proof:

Case $1$: If $S_B \subsetneq S_A$. Player $A$ would first use the letter that player $B$ doesn't have. Hence player $B$ can't form a palindrome during his turn. Player $A$ would then place whatever that player $B$ placed to end the game.

Case $2$: If player $A$ contains $2$ letters that player $B$ does not have. Player $A$ would use one such letter in his first move and player $B$ can't form a palindrome as he doesn't have this letter. Player $A$ then end the game by placing the same letter that he used in his first move.

Case $3$: If $S_A \subseteq S_B$. Whatever that player $A$ place, player $B$ just have to copy that to end the game.

Case $4$: If none of the above occur, we claim that player $B$ would win. During player $A$'s first move, he will use a letter that player $B$ doesn't have. Let's call this letter $l_A$. During player $B$'s first move, player $B$ will also use a letter that player $A$ doesn't have, call it $l_B$. Since case $2$ didn't happen, there is only one such copy of $l_A$. If player $A$ were to win the game, he has to form a palindrome of odd length, hence he has to place $l_A$ in the middle of the palindrome. However, he doesn't have $l_B$ which is necessary to form a palindrome. Hence there is no way for $A$ to win the game under this case.

Remark: OP's strategy left out case $1$.