この問題は \(O(N+Q+\sigma)\) 時間で解くことができます。

同じ文字になるインデックスを根つき森の形で保持することを考え、文字から連結成分（の根）を求められるようにしておきます。

まず、与えられた文字列に対応する根つき森および根の索引を \(O(N+\sigma)\) 時間で作ることができます。 先頭から文字列を走査し、すでに対応する森が存在するか見ながら頂点を追加していけばよいです。

また、操作ごとに定数回の演算で根つき森を更新することができます。 具体的には、\(c\) に対応する連結成分の根から \(d\) に対応する連結成分の根に辺を貼ればよいです。 実装の際はどちらかが存在しない場合や \(c=d\) の場合に注意してください。

すべての操作が終了したら、この森に対して適切に探索を行うことで \(O(N+Q)\) 時間で求める文字列を得ることができます。

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

#include <iostream>
#include <string>
#include <optional>
#include <vector>
#include <utility>

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

    unsigned Q;
    cin >> Q;

    // root[c] := 文字 c に対応する根
    // parent[i] := 頂点 i の親
    vector<optional<unsigned>> root(26), parent(N);

    for (unsigned i = 0; i < N; ++i) {
        const auto c = S[i] - 'a';
        if (root[c]) // c の根があれば
            parent[*root[c]] = i; // 今の c の根の親を i に
        root[c] = i; // c の根を i に
    }

    for (unsigned i = 0; i < Q; ++i) {
        char c, d;
        cin >> c >> d;
        c -= 'a';
        d -= 'a';

        if (c == d) // c = d なら
            continue; // 何もしない

        if (!root[c]) // いま c がなければ
            continue; // 何もしない

        if (!root[d]) { // いま d がなければ
            swap(root[d], root[c]); // c の根が新しく d の根になる
            continue;
        }

        // どちらもあれば
        parent[*exchange(root[c], nullopt)] = *root[d]; // c の根を d の根の子にし、c に対応する連結成分がなくなる
    }

    vector<optional<char>> result(N);
    for (unsigned c = 0; c < 26; ++c)
        if (root[c])
            result[*root[c]] = c + 'a'; // それぞれの根はそれぞれの文字に

    for (unsigned i = 0; i < N; ++i){
        if (!result[i]) { // まだ求まっていなければ
            vector<unsigned> index;
            auto now = i;
            while (!result[now]) // 値がわかるところまで
                index.emplace_back(exchange(now, *parent[now])); // 親をたどって
            for (const auto j : index)
                result[j] = result[now]; // たどった頂点の値を確定する
        }
        cout << *result[i];
    }
    cout << endl;

    return 0;
}