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

The following algorithm solves this problem.

• Prepare an empty stack, and initialize the answer as \(r=0\).
• For each character \(c\) of \(S\), in order from the front, repeat the following.
  • If \(c=\) A, push \(1\) onto the top of the stack.
  • If \(c=\) B:
    • Keep popping elements from the stack until a \(1\) comes out.
    • If a \(1\) came out of the stack, push \(2\) instead.
    • If no \(1\) came out of the stack, add \(1\) to \(r\).
  • If \(c=\) C:
    • Keep popping elements from the stack until a \(2\) comes out.
    • If no \(2\) came out of the stack, add \(1\) to \(r\).

The correctness can be explained as follows.

• The integers pushed onto the stack in this solution correspond to the following states.
  • \(1\) … A
  • \(2\) … AB
• The elements pushed onto the stack can be removed at any time.
• If an A appears, we push it onto the stack.
• If a B appears
  • If there was an A before it, we can combine it with that A to make it removable at any time.
  • If this B cannot be made removable at any time, then this B cannot be deleted, and the problem becomes independent before and after it.
• If a C appears
  • If there was an AB before it, we should combine it with that and delete them together.
  • If this C cannot be deleted, then this C cannot be deleted, and the problem becomes independent before and after it.

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;
    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;
}