Topcoder SRM 627 div1 HappyLettersDiv1 : 字元串

The Happy Letter game is played as follows: At the beginning, several players enter the field. Each player has a lowercase English letter on their back. The game is played in turns. In each turn, you select two players with different letters, and both selected players leave the field. The game ends once it is impossible to take another turn.

If there are some players left in the field at the end of the game, they must all have the same letter. That letter is called the winning letter. If there are no players left in the field at the end of the game, there is no winning letter.

You are given a string letters. The characters in letters are the characters carried by the players at the beginning of the game. Return a string with all possible winning letters. The letters in the returned string must be sorted in increasing order.

Class:

HappyLetterDiv1

Method:

getHappyLetters

Parameters:

string

Returns:

Method signature:

string getHappyLetters(string letters)

(be sure your method is public)

Time limit (s):

2.000

Memory limit (MB):

256

-

If there's no happy letter, return the empty string.

letters will contain between 1 and 50 elements.

Each element of letters will be a lowercase English letter ('a'-'z').

0)

Each of the three letters can be the winning letter. Here is one possibility how 'a' can be the winning letter: Let's number the players 0 through 8 in the order in which they appear in the input. We can then play the game as follows:

Send away players 1 ('a') and 8 ('c').

Send away players 2 ('b') and 6 ('c').

Send away players 7 ('c') and 0 ('a').

Send away players 5 ('c') and 3 ('b').

The only player left is player 4 ('a'), hence 'a' is the winning letter.

1)

Only letter 'a' can win.

2)

3)

No letter can win.

4)

Mean:

給你一個隻有小寫字母組成的字元串，每一輪你可以選擇兩個不相同的字元删去，如果最後還有剩下的字元，那麼這個字元就是winning letter，現在要你傳回可能是winning letter的字元組成的字元串，并按照升序排序。

analyse:

我們首先将每個字母出現的次數統計一遍，然後就是對26個小寫字母進行判斷，如果不包括本身，最多數量的那個字元的數量大于剩餘字元的數量，說明不可能滿足題目的要求(不同的字元互相比對)，否則就符合題目要求，加入ans字元串即可。

Time complexity：O(n)

Source code：