DoubleLetter | Topcoder Archive

Problem Statement

You are given a String S. You can modify this string by repeating the following process:

Find the leftmost occurrence of two consecutive letters in S that are the same.
If you found a pair of identical letters in the first step, delete those two letters from S.

For example, if S="aabccb", you can proceed as follows:

Find and erase "aa", producing the string "bccb".
Find and erase "cc", producing the string "bb".
Find and erase "bb", producing the empty string.

For S="axxyybac" you can do at most two steps, erasing "xx" first and "yy" next. Once you obtain the string "abac", you are done. Note that you cannot erase the two "a"s because they are not consecutive. You want to change S into an empty string by repeating the operation described above. Return "Possible" if you can do that, and "Impossible" otherwise.

Definition

Class:: DoubleLetter
Method:: ableToSolve
Parameters:: String
Returns:: String
Method signature:: String ableToSolve(String S)
(be sure your method is public)

Constraints

S will contain between 1 and 50 characters.
Each character in S will be a lowercase English letter ('a'-'z').

Examples

```
"aabccb"
```
```
Returns: "Possible"
```
```
"aabccbb"
```
```
Returns: "Impossible"
```
The process will terminate with a single 'b'.
```
"abcddcba"
```
```
Returns: "Possible"
```
"abcddcba" -> "abccba" -> "abba" -> "aa" -> "".
```
"abab"
```
```
Returns: "Impossible"
```
No two successive letters are the same, so we can't do any operation.
```
"aaaaaaaaaa"
```
```
Returns: "Possible"
```
```
"aababbabbaba"
```
```
Returns: "Impossible"
```
```
"zzxzxxzxxzzx"
```
```
Returns: "Possible"
```

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.