There are only two strings where A and B occur \(N\) times each: ABABAB... and BABABA.... Thus, the original problem can be answered by solving the following problem of the following form: how many operations are needed to turn \(S\) into \(T\)?

It is useless to perform the operation against a position with two identical characters. Therefore, the relative positions of A before and after the operation are always preserved. In other words, the \(k\)-th occurrence of A in \(S\) maps to the \(k\)-th occurrence of A in \(T\).

Let \(X_k\) be the position of the \(k\)-th occurrence of A in \(S\), and \(Y_k\) be that in \(T\). In one operation, the position of exactly one A changes exactly by one, so at least \(\sum_k |X_k-Y_k|\) operations is required to turn \(S\) into \(T\).

Conversely, the following procedure always achieves the minimum number, because each operation decreases \(\sum_k |X_k-Y_k|\) by one:

• Repeat the following until \(S\) coincides with \(T\):
  • For \(k\) with \(X_k<Y_k\) in ascending order, swap the \((X_k)\)-th and \((X_k+1)\)-th characters.
  • For \(k\) with \(X_k>Y_k\) in descending order, swap the \((X_k)\)-th and \((X_k-1)\)-th characters.

In this problem, only two strings ABABAB... and BABABA... are eligible for \(T\), corresponding to \(Y=(1,3,5,\ldots),(2,4,6,\ldots)\) respectively. Thus, the answer is \(\min\{\sum_k|X_k-(2k-1)|, \sum_k|X_k-2k|\}\). Since we can find \(X_k\) in \(O(N)\) time, the problem can be solved in \(O(N)\).