The following problem appeared in a local programming contest in my city. The problem is as follows:
There is a string S that consists of lowercase English alphabets, Two players — A and B are playing a game. In one turn, a player can choose either the character at the leftmost end or the character at the rightmost end. Suppose the player chose a character C, then all C's are removed from the string. Player A plays first. The player who removes the last characters of the string wins, i.e. if on removal of a certain character the string becomes empty, then the player who removed those letters wins. If both players play optimally, find out the player who wins.
EDIT: When the characters are removed, the player gets as many points as the number of characters that are removed. If both players play optimally, find the winner. (Both players try to maximize the points scored)
Uh... each turn, the number of distinct characters decreases by 1, so the first player wins if their number in the original string is odd and loses if it's even? Kinda simple.
WoW , thanks for problem .
Since there are only 26 lowercase English alphabets, so we can solve this problem with O(26^2) dp. We can count the appearance of every letters, it's the score one player can get. After that, we do some change to the S. Just save the leftmost appearance and rightmost appearance of each letters.(If one letter appears only once we still add two letters, however we know the value of this letter is 1) And dp[i][j] is the max score the the player of this turn can get when the string S's leftmost letter is i and the rightmost is j. You can brute force a map, next[2][i][j], what's next state if when remove the leftmost or rightmost letter. And you can get the answer you want.
Hope that helps.