ABC110Cの嘘解法

問題

ABC110 C問題 - String Transformation (300 点)

概要
英小文字のみからなる同じ長さの文字列S, Tが与えられます。
文字列Sに対して、次の操作を何度でも行うことができます。
0回以上操作を行って、SをTに一致させられるか判定してください。

操作
2つの異なる英小文字x, yを選び、Sに含まれる全てのxをyに、yをxに置き換える。

嘘解法

以下の嘘解法を多く見かけました。

嘘解法

from collections import Counter
 
s = input()
t = input()
 
c1 = Counter(s).most_common()
c2 = Counter(t).most_common()
 
for x, y in zip(c1, c2):
    if x[1] != y[1]:
        print("No")
        break
else:
    print("Yes")

テストケースで例えば

azzel
apple

に対して文字数のカウントが一致することを見ています。
文字数のカウントの個数に一致しないところがあれば、いくら操作を繰り返してもSはTに一致しません。

Sの文字数のカウント	Tの文字数のカウント	判定
(z, 2)	(p, 2)	2 == 2 一致
(a, 1)	(a, 1)	どちらも1個で一致
(e, 1)	(l, 1)	どちらも1個で一致
(l, 1)	(e, 1)	どちらも1個で一致

入力例に対してはすべて正しく判定でき、このコードを提出するとACに判定されます。
それでは、なぜこの方法は嘘解法なのでしょうか。

以下のような入力例を考えてみます。

aba
ccb

どのように操作を行ってもSはTに一致しませんが、上記のコードでは"Yes"と判定されてしまいます。

正しい解法

正しくは、以下の2つの条件を確認する必要があります。

• Sの中の同じ文字が、Tの別の文字に対応していない
• Tの中の同じ文字が、Sの別の文字に対応していない

これをコードで表現すると以下のようになります。

解答例

s = input()
t = input()

dict_st = {}
dict_ts = {}

for x, y in zip(s, t):
    if x not in dict_st:
        dict_st[x] = y
    else:
        if dict_st[x] != y:
            print("No")
            break

    if y not in dict_ts:
        dict_ts[y] = x
    else:
        if dict_ts[y] != x:
            print("No")
            break
else:
    print("Yes")

これを提出すると、正しくACとなります。
先ほどのS = "aba", T = "cca"のケースに対しても正しく"No"と判定できます。