WordSolitaire | Topcoder Archive

Problem Statement

Here is a solitaire game that can be played on a piece of paper. You start with a sequence of letters. Then you make a series of moves in which some of the letters are removed. If you can remove them all, you win.

There are two kinds of move:

Group-Of-Four: remove a group of 4 adjacent letters whose first and last letters match each other.
Pair: remove 2 adjacent matching letters.

For each move you must follow the following rules:

=> Your move MUST remove the earliest remaining letter that is removable.
=> If both kinds of move can remove the earliest remaining removable letter, you MUST use the Group-Of-Four rule.

We need to be able to simulate the game, given a starting sequence. Create a class Solitaire that contains a method getResult that is given a String start, the original sequence of letters, and that returns the final sequence as a String.

Definition

Class:: WordSolitaire
Method:: getResult
Parameters:: String
Returns:: String
Method signature:: String getResult(String start)
(be sure your method is public)

Constraints

start will contain between 1 and 50 characters, all uppercase letters 'A'-'Z'

Examples

```
"ABCCAACB"
```
```
Returns: "CB"
```
The first move is to remove the "CC" leaving "ABAACB", since the first "C" is the first letter in the sequence that can be removed. This leaves "ABAACB" as the sequence. Now the first "A" can be removed as part of a Group-Of-Four -- "ABAA" is removed leaving "CB". Now there are no more legal moves.
```
"ABCCBA"
```
```
Returns: ""
```
The first letter cannot be removed but the second letter is part of a Group-Of-Four so that group is removed leaving "AA". Now the first two letters can be removed as a Pair, leaving an empty String. Victory!

"ABCBABCBABCBABC"

Returns: "ABCBABCBABCBABC"

There are no moves at all.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.