ABBA | Topcoder Archive

Problem Statement

One day, Jamie noticed that many English words only use the letters A and B. Examples of such words include "AB" (short for abdominal), "BAA" (the noise a sheep makes), "AA" (a type of lava), and "ABBA" (a Swedish pop sensation).

Inspired by this observation, Jamie created a simple game. You are given two Strings: initial and target. The goal of the game is to find a sequence of valid moves that will change initial into target. There are two types of valid moves:

Add the letter A to the end of the string.
Reverse the string and then add the letter B to the end of the string.

Return "Possible" (quotes for clarity) if there is a sequence of valid moves that will change initial into target. Otherwise, return "Impossible".

Definition

Class:: ABBA
Method:: canObtain
Parameters:: String, String
Returns:: String
Method signature:: String canObtain(String initial, String target)
(be sure your method is public)

Constraints

The length of initial will be between 1 and 999, inclusive.
The length of target will be between 2 and 1000, inclusive.
target will be longer than initial.
Each character in initial and each character in target will be either 'A' or 'B'.

Examples

```
"B"
```
```
"ABBA"
```
```
Returns: "Possible"
```
Jamie can perform the following moves: Initially, the string is "B". Jamie adds an 'A' to the end of the string. Now the string is "BA". Jamie reverses the string and then adds a 'B' to the end of the string. Now the string is "ABB". Jamie adds an 'A' to the end of the string. Now the string is "ABBA". Since there is a sequence of moves which starts with "B" and creates the string "ABBA", the answer is "Possible".
```
"AB"
```
```
"ABB"
```
```
Returns: "Impossible"
```
The only strings of length 3 Jamie can create are "ABA" and "BAB".
```
"BBAB"
```
```
"ABABABABB"
```
```
Returns: "Impossible"
```

"BBBBABABBBBBBA"

"BBBBABABBABBBBBBABABBBBBBBBABAABBBAA"

Returns: "Possible"

```
"A"
```
```
"BB"
```
```
Returns: "Impossible"
```

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.