ビーズの状態としてあり得るのは、A, B からなる長さ \(N\) の列のみなので、高々 \(2^N\) 通りです。よってこれらを状態として BFS を行うことで最小操作回数を求めることができます。

遷移先が高々 \(O(N)\) 個であることから、計算量は \(O(N2^N)\) となります。

実装上は、A, B をそれぞれ 0, 1 に置き換えて二進法表記と解釈することで、ビーズの状態を整数と対応させると実装が容易になります。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int encode(string s){
  int ret = 0;
  for(int i=0; i<s.size(); i++){
    if(s[i] == 'B'){
      ret += 1<<i;
    }
  }
  return ret;
}

int main(){
  int n;
  cin >> n;
  string s, t;
  cin >> s >> t;

  vector<int>divisors;
  for(int i=1; i<=n; i++){
    if(n % i == 0){
      divisors.push_back(i);
    }
  }

  int NONE = -1;
  vector<int> dist(1<<n, NONE);

  int start = encode(s);
  dist[start] = 0;
  queue<int> q({start});
  while(q.size() > 0){
    int v = q.front(); q.pop();
    vector<int> cand;
    cand.push_back(v>>1 | (v&1)<<(n-1));
    cand.push_back((v<<1&((1<<n)-1)) | v>>(n-1));
    for(int d: divisors){
      int ret=0;
      for(int i=0; i<n/d; i++){
        ret += (v&((1<<d)-1))<<(d*i);
      }
      cand.push_back(ret);
    }
    for(int vv: cand){
      if(dist[vv] == NONE){
        dist[vv] = dist[v] + 1;
        q.push(vv);
      }
    }
  }

  cout << dist[encode(t)] << endl;
}

実装例 (Python)

N = int(input())
S = input()
T = input()

def encode(S):
  ret = 0
  for i, c in enumerate(S):
    if c == 'B':
      ret += 1<<i
  return ret

divisors = [i for i in range(1, N) if N%i==0]

NONE = -1
dist = [NONE] * (1<<N)

start = encode(S)
dist[start] = 0
q = [start]
for v in q:
  cand = []
  cand.append(v>>1 | (v&1)<<(N-1))
  cand.append((v<<1&((1<<N)-1)) | v>>(N-1))
  for d in divisors:
    cand.append(sum( (v&((1<<d)-1))<<(d*i) for i in range(N//d)))
  for vv in cand:
    if dist[vv] == NONE:
      dist[vv] = dist[v] + 1
      q.append(vv)

print(dist[encode(T)])