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

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

• 空のスタックを用意し、 解 \(r=|S|\) で初期化する。
• \(S\) の各文字 \(c\) について、後ろから順に以下を繰り返す。
  • \(c=\) C である場合
    • スタックの一番上に \(0\) を積む。
  • \(c=\) B である場合
    • スタックの一番上に \(0\) が積まれているならそれを取り出し、代わりに \(3\) を積む。
    • そうでないとき、スタックの一番上に \(2\) を積む。
  • \(c=\) A である場合
    • スタックの一番上に正整数が積まれている場合、それを取り出し \(r\) から減算する。
    • そうでないとき、 \(r\) から \(1\) 減算する。

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

• 解法内でスタックに積む整数は、以下の状態に対応する。
  • \(0\) … C
  • \(2\) … B
  • \(3\) … BC
• C が現れた場合、その C を消さなければその後ろの文字に手をつけられません。
• B が現れた場合
  • 直後が C であれば、 B を消す際に同時にその C を消せます。
  • 直後も B であれば、現れた B を消さなければその後ろの文字に手がつけられません。
• A が現れた場合、その A を残す意味はなく、直ちに消すべきです。
  • 後ろが C であればまとめて消すことはできませんが、 B あるいは BC であればまとめて消せます。

本解法の時間計算量は \(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;
    reverse(s.begin(),s.end());
    stack<int> st;
    int res=s.size();
    for(auto &nx : s){
      if(nx=='C'){
        st.push(0);
      }
      else if(nx=='B'){
        if(st.size()>0 && st.top()==0){st.pop(); st.push(3);}
        else{st.push(2);}
      }
      else{
        if(st.size()>0 && st.top()>0){res-=st.top(); st.pop();}
        else{res--;}
      }
    }
    cout << res << "\n";
  }
  return 0;
}