Topcoder ABBA editorial and solution

13-Mar-2019 • 3 min read

Hello readers!

In this humble post, we will be discussing how to solve topcoder ABBA codenamed problem. If you are directly coming to this blog post and wanted to read the problem description, please do so at topcoder.

At first sight, the problem seems pretty obvious. Most people with come up with a solution to check the presence of initial substring in target and consider it a possibility. But, if you look at a test case like below, it's easy to figure out that is not the correct solution.

initial - BA
target  - BBA

Substring solution fails for the above case. The solution to this problem would have been pretty easy if the reversing complexity has been removed. So, how do we go about solving this particular problem? Let's find out.

The idea is to backtrack from the target string's last character and go to the previous state. Once both the target and initial strings have same length, they should be identical if there is a possibility. Below is the code.

#include <bits/stdc++.h>

using namespace std;

class  ABBA {
public:
  string canObtain(string, string);
};

string ABBA::canObtain(string initial, string target) {
  while (target.length() > initial.length()) {
    int len = target.length();
    if (target[len-1] == 'A') {
      target = target.substr(0, len-1);
    } else {
      target = target.substr(0, len-1);
      reverse(target.begin(), target.end());
    }
  }

  return target == initial ? "Possible" : "Impossible";
}

Hope this helps. Comment down below if you need any further help.