Note that it doesn’t matter whether you replace a character before or after you move it, so we assume all operation 1s are performed before operation 2s.

It can be seen we should do operation 1 less than \(N\) times, as that just puts us at the same position as doing it \(0\) times. Now let’s say we fix how many times we should do operation 1. Then for each of the first \(\lfloor N/2 \rfloor\) characters, we can check it against its “pair”, i.e. the \(i\)-th character with the \((N+1-i)\)-th character. If it matches, we don’t need to change it, otherwise we pay \(B\) yen to change one of them to match.

This allows a \(O(N^2)\) brute-force solution.