Connection Status:
Competition Arena > ABBA

ABBA

SRM 663 · 2015-06-30 · by zxqfl

SRM 663 · 2015-06-30 · by zxqfl · Simple Search, Iteration, Simulation, String Manipulation
Class Name: ABBA
Return Type: String
Method Name: canObtain
Arg Types: (string, string)
Problem Statement

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".

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
0)
"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".

1)
"AB"
"ABB"
Returns: "Impossible"

The only strings of length 3 Jamie can create are "ABA" and "BAB".

2)
"BBAB"
"ABABABABB"
Returns: "Impossible"
3)
"BBBBABABBBBBBA"
"BBBBABABBABBBBBBABABBBBBBBBABAABBBAA"
Returns: "Possible"
4)
"A"
"BB"
Returns: "Impossible"

Submissions are judged against all 70 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ABBA with a public method string canObtain(string initial, string target) · 70 test cases · 2 s / 256 MB per case

Submitting as anonymous