Overview

For multiple strings, we perform “replace all occurrences of character \(a\) with character \(b\)” \(Q\) times, and efficiently compute the results for all strings.

Key Insight

If we naively apply each operation to every file and every character, a single replacement scans through all characters (up to \(10^6\)), and repeating this \(Q\) times (up to \(10^5\)) results in \(O(Q \cdot \sum |S_i|)\), which is clearly too slow.

The crucial observation is that if we can determine “what each alphabet letter ultimately maps to,” then we only need to transform each string once at the very end.

However, replacements happen sequentially, so for example: - 1st operation: a -> b - 2nd operation: b -> c

Then ultimately a becomes c. This is because a becomes b after the 1st operation, and then follows whatever happens to b from the 2nd operation onward.

This dependency can be easily handled by processing the operations in reverse order. When thinking backwards, the relationship “if there was an operation a -> b, then the final result for a is the same as the final result for b” holds true.

Algorithm

1. Read all replacement operations \((a_j, b_j)\) and store them in an array.
2. Prepare an array mp[x] representing “what character x (0–25) ultimately becomes,” initialized as mp[x] = x.
3. Process the operations in reverse order. When viewed in reverse, the operation a -> b is handled by updating:
   • mp[a] = mp[b] This expresses that “character a ultimately goes to whatever character b ultimately becomes.”
4. Once mp is complete, convert each character in every string according to mp and output the result.
   • In the implementation, str.maketrans and translate are used for fast single-pass conversion.

(Example) If the operations are a->b, b->c, processing in reverse: - First b->c: mp[b] = mp[c] = c - Then a->b: mp[a] = mp[b] = c

This correctly determines that a ultimately maps to c.

Complexity

• Time complexity: \(O(Q + \sum_{i=1}^{N} |S_i| + 26)\) (Building the mapping is \(O(Q)\), string conversion totals \(O(\sum |S_i|)\))
• Space complexity: \(O(Q + \sum_{i=1}^{N} |S_i|)\) (For storing input and operations; the mapping is \(O(26)\) and negligible)

Implementation Notes

• Reverse-order processing is the core idea: by performing mp[a] = mp[b] from back to front, the effects of subsequent replacements are naturally incorporated.

• In Python, reading all input at once with sys.stdin.buffer.read() ensures stability when handling large inputs.

• For character conversion, using translate is more concise and faster than replacing characters one by one in a loop.

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    it = iter(data)
    N = int(next(it))
    Q = int(next(it))

    strings = [next(it).decode() for _ in range(N)]

    ops = []
    for _ in range(Q):
        a = next(it).decode()
        b = next(it).decode()
        ops.append((ord(a) - 97, ord(b) - 97))

    mp = list(range(26))
    for a, b in reversed(ops):
        mp[a] = mp[b]

    mapped = ''.join(chr(97 + mp[i]) for i in range(26))
    table = str.maketrans('abcdefghijklmnopqrstuvwxyz', mapped)

    out = [s.translate(table) for s in strings]
    sys.stdout.write('\n'.join(out))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.