DWITE Online Computer Programming Contest, February 2011, Problem 4
Over the years, many word games have been invented. However, most of them involve actually knowing the definitions of these words, and this can get kind of frustrating. So you decided to create a word game that doesn't involve knowing what words actually mean:
- You start out with a word.
- If there is a run of length 2 or more of some letter, you can remove the whole run from the word all together (e.g. In the word 'GREEN', you can remove the two E's to get 'GRN').
- You keep removing runs of the same letters like above until you can't find any such runs.
- If the word is now empty, then you call the word you started with 'solvable'. If what remains isn't empty, then the word you started with is 'unsolvable'.
You then decide to make a program to help determine whether certain given words are solvable or not.
The input will contain 5 test cases. Each test case is a single line with 5 words separated by a single space, where each of these words consist of up to 150 uppercase characters.
The output should contain 5 lines. Each line consists of some 5 letter combination of 'S' or 'U', where the th letter is a 'S' if the th word in the input was solvable, or a 'U' if the th word in the input was unsolvable.
Note: there might be more than one solution to a particular word.
Explanation of the first test case: 'GREEN' is clearly unsolvable, since after removing the 'E's you are left with the string 'GRN'. As for 'ABBA', removing the 'B's yields 'AA'. You can then remove the 'A's to get rid of the whole word (making it solvable). 'POST and 'LEMONADE' aren't solvable either, as there aren't any runs to remove in the first place. 'ROAAAOR' is solvable, as you can remove the 'A's to get 'ROOR', and then you can remove the 'O's to get 'RR', and finally you remove the 'R's to get rid of the whole word.
GREEN ABBA POST LEMONADE ROAAAOR