ABBADiv1 | 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.
Add the letter B to the end of the string and then reverse the entire string. (After the reversal the newly-added B becomes the first character 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:: ABBADiv1
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 49, inclusive.
The length of target will be between 2 and 50, inclusive.
target will be longer than initial.
Each character in initial and each character in target will be either 'A' or 'B'.

Examples

```
"A"
```
```
"BABA"
```
```
Returns: "Possible"
```
Jamie can perform the following moves: Initially, the string is "A". Jamie adds a 'B' to the end of the string and then reverses the string. Now the string is "BA". Jamie adds a 'B' to the end of the string and then reverses the string. Now the string is "BAB". Jamie adds an 'A' to the end of the string. Now the string is "BABA". Since there is a sequence of moves which starts with "A" and creates the string "BABA", the answer is "Possible".
```
"BAAAAABAA"
```
```
"BAABAAAAAB"
```
```
Returns: "Possible"
```
Jamie can add a 'B' to the end of the string and then reverse the string.
```
"A"
```
```
"ABBA"
```
```
Returns: "Impossible"
```

"AAABBAABB"

"BAABAAABAABAABBBAAAAAABBAABBBBBBBABB"

Returns: "Possible"

"AAABAAABB"

"BAABAAABAABAABBBAAAAAABBAABBBBBBBABB"

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.