ABC342 C問題の解説（Python）

はじめに

この記事では、ABC342のC問題を解説していきます。

ABC（AtCoder Beginner Contest）とは、AtCoderが開催している、競技プログラミングコンテストです。

ABC342　C – Many Replacement

問題

問題

英小文字からなる長さNの文字列Sが与えられます。

文字列Sに対して操作をQ回行います。i回目の操作は、次のような内容です。

• Sに含まれる文字 \(c_i\)​ をすべて文字 \(d_i\)​​ で置き換える

すべての操作が終わったあとの文字列Sを出力する問題です。

制約

• \(1 \leqq N \leqq 2×10^5 \)
• \(1 \leqq Q \leqq 2×10^5 \)

思考の筋道

文字列Sの長さ、操作回数ともに最大で2×10^5です。そのため、素直に文字列Sに各操作を行っていくのでは、TLE（制限時間超過）になってしまいます。

この問題で求める必要があるのは、すべての操作が終わったあとのSです。途中のSは必要ありません。

であれば、Sそのものではなく、26種類の英小文字に対して各操作を行っていきましょう。これであれば26文字だけなので問題ありません。

各英小文字が操作終了時にどの文字に置き換えられているかが得られます。あとはそれに従って、文字列Sを変換すればよいですね。

maketransという関数でどのように変換するかの対応を作成し、translateという関数で実際に文字列に対して変換を行います。このような関数はすぐ取り出せるように、自分用のメモにストックしておくのが良いかもしれません。

コード

import string
N = int(input())
S = input()
Q = int(input())

alphabet = string.ascii_lowercase
goal = string.ascii_lowercase

for i in range(Q):
    c, d = map(str, input().split())
    goal = goal.replace(c, d)

translation = str.maketrans(alphabet, goal)

S = S.translate(translation)
print(S)

以上、ABC342のC問題の解説でした！

では、またね。

リンク