In a contiguous substring of \(S\), we call a maximal string of the form A…ARC…C a block. Also, we call the blocks in \(S\) Block \(1, 2, \ldots, M\) from left to right.

When no more operation is possible in a block, it has one of the forms A…AC…C, R, A…AR, RC…C. From this, we can see that an operation never combines multiple blocks into one.

The above observation allows us to rephrase the problem into the following, where \(X_i\) is \(\mathrm{min}\)(number of A’s, number of C’s).

You are given a sequence of positive integers \(X=(X_1,X_2,\ldots,X_M)\). At most how many times can the operation below be performed?

• In an odd-numbered operation, choose a positive element from \(X\) and decrease it by \(1\).
• In an even-numbered operation, choose a positive element from \(X\) and delete it.

We will consider this problem. It is easy to show the following: in an odd-numbered operation, it is optimal to choose the smallest element at least \(2\) if it exists; in an even-numbered operation, it is optimal to delete the smallest element.

This greedy strategy solves the problem in \(\mathrm{Ο}(N\log N)\) time.

We can also solve it in linear time. Let us consider an upper bound for the number of operations.

Since each even-numbered operation removes a positive element from \(X\), there can be at most \(2M\) operations. Also, since each operation decreases the sum of \(X\) at least \(1\), there can be at most \(\sum_i X_i\) operations.

Therefore, \(\mathrm{min}(2M, \sum_i X_i)\) is an upper bound for the number of operations, which turns out to be always achievable.

Thus, the problem is solved in \(\mathrm{Ο}(N)\).