愚直に置換処理を行うと、1 回あたり \(\Omega(\sum_i |S_i|)\) 時間かかり、全体で \(\Omega(Q\sum_i |S_i|)\) 時間かかるため TLE します。

重要なのは「どの文字が最終的にどの文字に置換されるか」の情報のみです。これは各英小文字に対して実際置換処理を行うことで文字種数を \(\sigma=26\) として \(O(\sigma Q)\) 時間で求めることができます。これを用いて最後に1度だけ実際に各文字列の置換を行うことは \(O(\sum_i |S_i|)\) 時間でできるため、全体で \(O(\sigma Q+\sum_i |S_i|)\) 時間でこの問題を解くことができます。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main() {
  int n, q;
  cin >> n >> q;
  vector<string> s(n);
  for(int i=0; i<n; i++) cin >> s[i];

  string alphabet = "abcdefghijklmnopqrstuvwxyz";
  for(int i=0; i<q; i++){
    char a, b;
    cin >> a >> b;
    replace(alphabet.begin(), alphabet.end(), a, b);
  }

  for(int i=0; i<n; i++){
    string ans = "";
    for(char c: s[i]){
      int idx = c - 'a';
      ans += alphabet[idx];
    }
    cout << ans << endl;
  }
}

実装例 (Python)

N, Q = map(int,input().split())
S = [input() for _ in range(N)]
alphabet = "abcdefghijklmnopqrstuvwxyz"
for _ in range(Q):
  a, b = input().split()
  alphabet = alphabet.replace(a,b)

for s in S:
  ans = []
  for c in s:
    i = ord(c) - ord('a')
    ans.append(alphabet[i])
  print("".join(ans))