\(S\) と \(T\) に含まれる 0 と 1 の個数が一致しない場合、明らかに \(S\) を \(T\) に作り替えることはできません。 以下、\(S\) と \(T\) は同数の 0 と 1 を含むものとします。

0 と 1 のみからなる文字列 \(U\) に対して、 \(U\) の 0 の極大な各 run 0\(^l\) を、\(\lfloor l/X \rfloor\) 個の A と \((l \bmod X)\) 個の 0 を連節したものに置き換え、 同様に \(U\) の 1 の極大な各 run 1\(^l\) を、\(\lfloor l/Y \rfloor\) 個の B と \((l \bmod Y)\) 個の 1 を連節したものに置き換えて得られる文字列を \(U\) の圧縮列と呼ぶことにします。

文字列 \(U\) が問題文中の操作の繰り返しで文字列 \(U'\) へ作り替えられることは、\(U\) の圧縮列が \(U'\) の圧縮列へと下記の \(3\) 種類の基本操作の繰り返しによって作り替えられることと同値です。

• 隣接する 0 と A を 交換する。
• 隣接する 1 と B を交換する。
• 隣接する A と B を交換する。

（特に、圧縮列に対して基本操作を繰り返しても、\(X\) 個の 0 または \(Y\) 個の 1 が連続することはないことが、0, 1 はそれぞれ A, B 以外と交換できないことからわかります。）

よって、本問題は「 \(S\) の圧縮列に基本操作を繰り返して \(T\) の圧縮列に作り替えられるか」という問題です。 以下、簡単のために、\(S\) の圧縮列と \(T\) の圧縮列を単に \(S, T\) と呼びます。

基本操作では、0 と 1 どうし、0 と B どうし、1 と A どうしはそれぞれ交換できないため、下記の [A], [B], [C] は基本操作によって不変です。

• [A] 全ての 0 と 1 を順番を変えずに抜き出した部分列
• [B] それぞれの 0（および文字列全体の両端）同士の間にある B の個数
• [C] それぞれの 1（および文字列全体の両端）同士の間にある A の個数

そのため、\(S\) を \(T\) に作り替えられるためには、少なくとも \(S\) と \(T\) の不変量 [A], [B], [C] がすべて一致する必要があります。

反対に、\(S\) と \(T\) のこれらが一致することは、\(S\) を \(T\) に作り替えられるための十分条件でもあることを以下で示します。

まず、\(S\) に対して「基本操作によって下記の \(3\) 種類の操作のいずれかを行う」ことを（任意の順番で）可能な限り行い、これ以上そのような操作が行えない文字列 \(S'\) が得られたとします。

• 連続部分文字列 0A を A0 に置き換える。
• 連続部分文字列 B1 を 1B に置き換える。
• 連続部分文字列 BA を AB に置き換える。

ここで、上記の操作を繰り返せる回数は有限回であって必ずそのような \(S'\) が得られることが、（連続とは限らない）部分列 0A、 1B、 BA の個数が操作のたびに減少することからわかります。

\(T\) に対しても同様の手順を行なって文字列 \(T'\) が得られたとします。

ここで、実は \(S\) と \(T\) の不変量 [A], [B], [C] が一致しているならば、\(S\) から \(S'\) 、\(T\) から \(T'\) を作る際の手順によらず、必ず \(S' = T'\) が成り立つことを以下で示します。 これが示されることにより、基本操作の可逆性から \(T'\) を \(T\) に作り替えることも可能であるため、\(S \to S' = T' \to T\) の通りに、\(S\) を \(T\) に作り替えられることがわかり、証明が完了します。

そのためには、上で作った \(S', T'\) が、その作り方から

\((\star)\) 0A、 B1、 BA のいずれをも連続部分文字列として含まない

ことに注意すると、「 \(S\) が与えられたとき、\(S\) と不変量 [A], [B], [C] が同一である上で条件 \((\star)\) を満たす文字列 \(S'\) は一意である」ことを以下で示せば十分です。

まず、不変量 [A] の 0 と 1 のみからなる文字列を \(R\) とおくと、\(S'\) は \(R\) の各文字の間または文字列全体の前後にいくつかの A や B を挿入して得られるものに限られます。

ここで、\(S'\) は 0A を連続部分列として含まないことから、 \(R\) に対して A を挿入できるのは 1 の直後（または文字列全体の先頭）に限られます。 また、不変量 [C] が指定されているため、\(R\) の各 1 の直後（および文字列全体の先頭）に挿入される A の個数は一意に定まります。 同様に、\(R\) に対して B を挿入できるのは 0 の直前（または文字列全体の末尾）に限られ、その各位置に挿入される B の個数は指定された不変量 [B] に基づいて一意に定まります。

さらに、\(R\) の文字の隙間（および文字列の先頭・末尾）のうち A と B が両方とも挿入される箇所におけるそれらの挿入順は、全ての A を全ての B より左に並べるという順番に一意に定まることが、\(S'\) が BA を 含まないという条件から導かれます。

以上より、\(S\) が与えられたとき、\(S\) と不変量 [A], [B], [C] が同一である上で \((\star)\) を満たす文字列 \(S'\) は一意です。