In this editorial, we take the approach of examining \(S\) from the back.

The following algorithm solves this problem.

• Prepare an empty stack, and initialize the answer as \(r=|S|\).
• For each character \(c\) of \(S\), in order from the back, repeat the following.
  • If \(c=\) C:
    • Push \(0\) onto the top of the stack.
  • If \(c=\) B:
    • If \(0\) is on top of the stack, pop it and push \(3\) instead.
    • Otherwise, push \(2\) onto the top of the stack.
  • If \(c=\) A:
    • If a positive integer is on top of the stack, pop it and subtract it from \(r\).
    • Otherwise, subtract \(1\) from \(r\).

The correctness can be explained as follows.

• The integers pushed onto the stack in this solution correspond to the following states.
  • \(0\) … C
  • \(2\) … B
  • \(3\) … BC
• If a C appears, we cannot touch the characters after it unless we delete that C.
• If a B appears
  • If it is immediately followed by C, we can delete that C at the same time as deleting the B.
  • If it is immediately followed by another B, we cannot touch the characters after it unless we delete the B that appeared.
• If an A appears, there is no reason to keep that A, and it should be deleted immediately.
  • If it is followed by C, we cannot delete them together, but if it is followed by B or BC, we can delete them together.

The time complexity of this solution is \(O(|S|)\).

Sample Implementation (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;
}