[Q] A - Yet Another AB Problem

考察
1. どうしても作れないケースを考える。

サンプル1
2
S:AB
T:BA

1. Sの先頭をBにしたいけど、先頭より前でAに変えるような場所がないのでできない。
2. Tの末尾をAにしたいけど、末尾より後でBに変えるような場所がないのでできない。

サンプル2
6
S:BBABAA
T:BBBAAA

これもできない。
1. S[2]をBにしたいけど、S[0]もS[1]もAにできない。
2. S[3]をAにしたいけど、S[4]もS[5]もBにできない。

a. 先頭から見て、SのAより先にTのAが出現したらOK。
SのAがTのAより先にきてしまうような、S[x]=A && T[x]=B となるindex_xが見つかったらNG。
b. 末尾から見て、SのBより先にTのBが出現したらOK。
SのBがTのBより先にきてしまうような、S[x]=B && T[x]=Aとなるindex_xが見つかったらNG。

2. できる文字列と分かった場合

入力例1
5
BAABA
AABAB
~ ~~~ の4か所を
A BAB に変えたい。

A-Bの順番に消去ペアにすることはできる。
なので、
1. Aに変えたい場所waと、Bに変えたい箇所wbを都度カウントアップ
2. wbを加算するときに、waが存在しているなら1ペアとみなせばいい。

実装

int main() {
  cincout();
  ll N;
  string S, T;
  cin >> N >> S >> T;

  // 1. 文字列が作れないパターンを検知する
  rep(i, N){ // 先頭から見て行って、TにAがあるか探す。
    if (T[i] == 'B' && S[i] == 'A'){
      cout << -1 << endl;
      return 0;
    }
    // TにAが見つかったら問題ない。
    if (T[i] == 'A') break;
  }
  rrep(i, N){
    if (T[i] == 'A' && S[i] == 'B'){
      cout << -1 << endl;
      return 0;
    }
    if (T[i] == 'B') break;
  }

  // 2. 作れる文字列と分かったので、操作回数を調べる
  ll wa = 0, wb = 0;
  rep(i, N){
    if (S[i] != T[i]){
      if (S[i] == 'B') wa++;
      else{
        wb++;
        if (wa > 0) --wa;
      }
    }
  }
  cout << (wa + wb) << endl;
}

https://atcoder.jp/contests/arc170/submissions/49543742