この解説では、 \(S\) を前から調べる方針を取ります。

以下のアルゴリズムでこの問題に正解できます。

• 空のスタックを用意し、 解 \(r=0\) で初期化する。
• \(S\) の各文字 \(c\) について、前から順に以下を繰り返す。
  • \(c=\) A である場合、スタックの一番上に \(1\) を積む。
  • \(c=\) B である場合
    • スタックから \(1\) が出てくるまで要素を取り出し続ける。
    • スタックから \(1\) が出てきた場合、代わりに \(2\) を入れる。
    • スタックから \(1\) が出てこなかった場合、 \(r\) に \(1\) 加算する。
  • \(c=\) C である場合
    • スタックから \(2\) が出てくるまで要素を取り出し続ける。
    • スタックから \(2\) が出てこなかった場合、 \(r\) に \(1\) 加算する。

正当性は以下の通りに説明できます。

• 解法内でスタックに積む整数は、以下の状態に対応する。
  • \(1\) … A
  • \(2\) … AB
• スタックに積まれた要素はいつでも取り除くことができます。
• A が現れた場合、それをスタックに積みます。
• B が現れた場合
  • もし前に A があった場合はそれと組み合わせていつでも取り除ける状態にできます。
  • もしこの B をいつでも取り除ける状態にできない場合はその B を消すことはできず、その前後で問題が独立します。
• C が現れた場合
  • もし前に AB があった場合はそれと組み合わせて取り除くべきです。
  • もしこの C を取り除けない場合はその C を消すことはできず、その前後で問題が独立します。

本解法の時間計算量は \(O(|S|)\) です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t;
  cin >> t;
  while(t--){
    string s;
    cin >> s;
    stack<int> st;
    int res=0;
    for(auto &nx : s){
      if(nx=='A'){st.push(1);}
      else if(nx=='B'){
        while(st.size()>0 && st.top()!=1){st.pop();}
        if(st.size()>0){
          st.pop();
          st.push(2);
        }
        else{res++;}
      }
      else{
        while(st.size()>0 && st.top()!=2){st.pop();}
        if(st.size()>0){
          st.pop();
        }
        else{res++;}
      }
    }
    cout << res << "\n";
  }
  return 0;
}