ABC110 C. String Transformation

問題

英小文字からなる文字列S, Tがある。
Sに対して、次の操作を0回以上行える。

• 2つの異なる英小文字c1, c2を選び、Sに含まれるすべてのc1をc2に、c2をc1に同時に置換する

操作を行うことでSをTにすることができるか？

制約

• 1 <= Sの長さ <= 2 * 10^5
• Sの長さ = Tの長さ

解法

Sの長さは結構長いが、すべての同じ文字が同時に置換されるので、高々26文字を考えればよい。
題意から素直に「S側の文字aを(T側に対応する)文字xにする」ということを考える。

まず、「S側のある文字aが、文字x, y, ...(2文字以上)にする」ようなS,Tが与えられたら、操作不可能なので、「できない」。
したがって、「S側の文字aを文字x(1文字)にする」ことができる必要がある。

与えられたS, Tから「a -> x」「b -> y」「c -> z」のような文字の変換表が作れたら、素直にチェックすればよい。

S: abcxyz
T: xyzghi

S, Tは、変換表にある文字だけに圧縮できるので上記のようになっているはず。これを左から実際に変換していく。
このとき、「xをxにする」ようなモノはいじる必要がないので、除いておいてよい。

まず、「aをxにする」ことを考え、操作(a,x)をする。
すると、Sは「xbcayz」になり、1文字目が確定する。
置き換えた「文字x」は2文字目以降の操作では使えないので、もしでてくるようなら「できない」。
2文字目以降も同様に繰り返して最後まで変換できるなら、「できる」になる。

解法2

AtCoder Beginner Contest 110 解説放送 - YouTube

SからTにするというのは、Sの文字をTにある文字に対応させるということなので、以下のような(1対1)対応関係を考えて、右側の文字を操作によって入れ替えていくことに相当する。

a -> a
b -> b
c -> c
d -> d
...
z -> z

たとえば、「S側でaだったものをcにしたい」場合は、対応関係の右側でcだったところとswapして、

a -> c
b -> b
c -> a
d -> d
...
z -> z

続けて「S側でcだったものをdにしたい」場合は、

a -> c
b -> b
c -> d
d -> a
...
z -> z

のようにしていることが、操作をしていることに対応している。

上記の操作が問題なくできれば「できる」が、うまくいかないケースを考える。
対応関係の左側と右側それぞれで2種類以上の文字への対応が存在する場合「できない」。
1つ目は、「S側でaだったものをxにしたい」と「S側でaだったものをyにしたい」が発生する場合は「できない」ことがわかる。
2つ目は、「S側でaだったものをxにしたい」と「S側でbだったものをxにしたい」が発生する場合は「できない」。
これらを調べればよい。