最終的な \(S\) の \(i\) 文字目 \(S _ i\) は、はじめ \(S _ i\) が何であったかのみによって決まります。

よって、すべての英小文字に対して最終的にどの文字になるかがわかれば、その情報を用いて答えを出すことができます。
\(S\) に対して操作を行う代わりに abcdefghijklmnopqrstuvwxyz などに対して操作を行うと考えることもできます。

計算量はアルファベットサイズを \(\sigma(=26)\) として \(O(\sigma(N+Q))\) などになります。

実装例は以下のようになります。

from string import ascii_lowercase

N = int(input())
S = input()

Q = int(input())

# 変換前と変換後の文字列を作る
# 'abcdefghijklmnopqrstuvwxyz' で初期化
mapping_from = ascii_lowercase
mapping_to = ascii_lowercase

for _ in range(Q):
    c, d = input().split()
    mapping_to = mapping_to.replace(c, d) # c を d に置き換える

# 対応する文字をそれぞれ置き換える
print(S.translate(str.maketrans(mapping_from, mapping_to)))

#include <iostream>
#include <string>

int main() {
    using namespace std;
    unsigned N;
    cin >> N;
    string S;
    cin >> S;

    unsigned Q;
    cin >> Q;

    // 変換前と変換後の文字列を作る
    string from, to;
    // すべての英小文字が含まれる文字列で初期化
    from = to = "abcdefghijklmnopqrstuvwxyz"s;

    for (unsigned i = 0; i < Q; ++i) {
        char c, d;
        cin >> c >> d;
        for (auto &&m : to)
            if (m == c) // c があったら
                m = d; // d に変換
    }

    for (const auto c : S)
        for (unsigned i = 0; i < 26; ++i)
            if (c == from[i]) // 変換前の文字から
                cout << to[i]; // 変換後の文字を求める
    cout << endl;

    return 0;
}