AtCoder:ABC110-C(String Transformation)を解いた-ぐぐりらにっき

SとTという二つの同じ長さの文字列が与えられ、文字を二つ決めて、Sに含まれる全てのその二つの文字をswapするという操作を行う。

この操作を行ってSをTに変えられるかどうかを判定する問題。

## 考察
普通にシミュレーションする(先頭から見ていって、毎回これまでに作用させた変換を見に行って変換していくと)と、$O(N^2)$かかる。

じゃあどうやんだ、ってなってからいろいろ実験するも、うまくいかず。

実験してる最中も間違えて実験してたりしたので変な考えにはまってしまった。
ちゃんと実験しよう。。。

$c_1$と$c_2$を選んで変換するときに、間違えて$T$の方も変換したりしてたので、ダメな例もうまくいくなあ、となってはまったのが原因。

## 解法

ちゃんと実験すれば、SからTへ違う文字から同じ文字へ写像されるとダメだし、ある文字から複数の文字へ写像するのもだめで、そういうのがない一対一の変換ができればおっけー、ということに気づく。

普通にやろうとすると、前者の「SからTへ違う文字から同じ文字へ写像されるとダメ」をチェックするのが$O(N)$かかるので全体で$O(N^2)$。

解説にもあるとおり、SからTの写像をみるのと同じようにTからSをみることをすれば$O(N+N)=O(N)$ですみます。

```python
S = input()
T = input()

def check(A, B[Numeron App](https://numeron-app.herokuapp.com)[i]
        elif d[A[i]] != B[i]:
            return False
    return True

print("Yes" if check(S, T) and check(T, S) else "No")

```

## 感想とか

S=ab
と
T=ba

のときとか、確かに{a => b, b => a}という写像を考えればいいのだけど、実際に操作する際には(a,b)を指定したら一回でこの変換が行われるわけで、なんか違和感がある。

操作の回数と、置換の回数が一致しないのが変なのかな。

ここにギャップがあって解けなかったんだとも思う。
同じ操作だけど別の置換として扱うのかあ。

今回は一致させることができるかどうか、を出力する問題だったけれど、一致させるのに必要な回数を求める問題だと$O(N)$で解くことはできるんだろうか。

AtCoder:ABC110-C(String Transformation)を解いた