Overview

The initial state is RR...RBB...B. If the number of Rs contained in the target string \(T\) is not \(A\), it is impossible; otherwise, the answer is the number of occurrences of BR in \(T\).

Analysis

First, if the number of Rs in \(T\) is not \(A\), the composition of cars differs from the initial state, so no matter how we rearrange them, we cannot produce \(T\).
In this case, the answer is -1.

From here on, we assume the number of Rs is \(A\).

The key observation is the number of BR occurrences in the string.

For example,

RRBB      -> number of BR is 0
RBBR      -> number of BR is 1
BRBR      -> number of BR is 2
BBRRBB    -> number of BR is 1

In the initial state RR...RBB...B, there are no BR occurrences.
This is because while there is a boundary RB where R is followed by B, there is no boundary BR where B is followed by R.

Here, one operation can increase the number of BR by at most \(1\).

Looking at the operation in terms of blocks of the string, if we represent a certain state as

U V W

then the operation of detaching the tail block \(W\) and inserting it before \(V\) can be viewed as

U V W -> U W V

The adjacency relationships that can change are only at the block boundaries.
Since the internal ordering does not change, the number of BR can increase by at most \(1\) per operation.

Therefore, since the number of BR in the initial state is \(0\), if the target \(T\) has \(c\) occurrences of BR, at least \(c\) operations are required.

Next, let’s consider that it is always achievable in exactly \(c\) operations.

Operations can also be performed in reverse with the same format.
That is,

U V W -> U W V

The reverse of this operation is:

U W V -> U V W

which can also be realized as an operation that detaches the tail block \(V\) and inserts it somewhere in the middle.

So, let’s consider going from the target string \(T\) back to the initial state RR...RBB...B.

If \(T\) contains BR, focus on the rightmost BR.
That part has the form where a consecutive block of Bs is followed by a consecutive block of Rs.

For example, it can be represented as:

U B...B R...R B...B

Here, if we detach the tail portion

R...R B...B

and move it before the preceding B...B, we get:

U R...R B...B B...B

and we have eliminated one BR that we were focusing on.

By repeating this, we can reduce the number of BR by one per operation.
Eventually, when the number of BR reaches \(0\), the string necessarily takes the form

RR...RBB...B

Therefore, we can go from \(T\) back to the initial state in exactly as many operations as the number of BR occurrences.
Since operations are also possible in reverse, we can reach \(T\) from the initial state in the same number of operations.

Thus, the answer is

the number of BR occurrences in \(T\).

Algorithm

1. Receive \(A, B, T\) as input.
2. Count the number of Rs in \(T\).
3. If that count differs from \(A\), output -1.
4. Otherwise, count and output the number of occurrences of the substring BR in \(T\).

For example,

A = 2, B = 2
T = BRBR

In this case, BR appears 2 times, so the answer is \(2\).

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

Implementation Notes

Since \(N\) can be as large as \(10^7\), repeatedly processing the entire string or simulating the operations will not finish in time.

In Python, handling the input as bytes is faster.

T.count(b'R')
T.count(b'BR')

Using these, you can efficiently count the number of Rs and BR occurrences, respectively.

Source Code

import sys

def main():
    input = sys.stdin.buffer.readline
    A, B = map(int, input().split())
    T = input().strip()

    if T.count(b'R') != A:
        print(-1)
    else:
        print(T.count(b'BR'))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.