The \(i\)-th character \(S_i\) of the resulting \(S\) only depends on the initial \(S _ i\).

Thus, if you know which lowercase English letter eventually becomes which, you can use the mapping to find the answer.
Essentially, we may perform operations against abcdefghijklmnopqrstuvwxyz instead of \(S\).

The computational complexity is \(O(\sigma(N+Q))\), where the alphabet size \(\sigma(=26)\).

The sample code is as follows.

from string import ascii_lowercase

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

Q = int(input())

# Construct strings before and after conversion
# Initialize with 'abcdefghijklmnopqrstuvwxyz'
mapping_from = ascii_lowercase
mapping_to = ascii_lowercase

for _ in range(Q):
    c, d = input().split()
    mapping_to = mapping_to.replace(c, d) # Replace c with d

# Replace each character to corresponding operation
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;

    // Construct strings before and after conversion
    string from, to;
    // Initialize them with strings that contain all lowercase English alphabet
    from = to = "abcdefghijklmnopqrstuvwxyz"s;

    for (unsigned i = 0; i < Q; ++i) {
        char c, d;
        cin >> c >> d;
        for (auto &&m : to)
            if (m == c) // For each occurrence of c,
                m = d; // replace it with d
    }

    for (const auto c : S)
        for (unsigned i = 0; i < 26; ++i)
            if (c == from[i]) // From the string before conversion,
                cout << to[i]; // find the string after conversion
    cout << endl;

    return 0;
}