Overview

Given \(N\) strings, we perform \(Q\) operations that replace a specific character with another character. The problem asks us to output the final strings after all operations are complete.

Analysis

The most straightforward approach is to “scan all strings and replace characters for each operation.” However, if we let \(L = \sum |S_i|\) be the total length of all strings, the time complexity of this approach is \(O(Q \times L)\). In this problem, \(Q = 10^5\) and \(L = 10^6\), so in the worst case approximately \(10^{11}\) operations would be needed, which will not finish within the time limit.

Here, we focus on the key observation that “there are only 26 types of characters (lowercase English letters).” Instead of rewriting the strings themselves repeatedly, we consider efficiently computing only the correspondence (mapping) of “which character ultimately becomes which character.”

In this solution, we process the operations in reverse order (from the last to the first) to determine the “final destination” of each character. For example, if at some point there is an operation “replace character a with b”, we can think of character a at that point as changing to “the character that b ultimately ends up as after all subsequent operations.”

Algorithm

1. Initialize the mapping: Prepare an array mapping of length 26, initialized so that each character maps to itself (a maps to a, b maps to b, …).
2. Process operations in reverse order: Look at operations \((a_j, b_j)\) from the \(Q\)-th to the \(1\)-st in order.
   • Update mapping[a_j] = mapping[b_j].
   • This records the relationship that “character \(a_j\) at this point ultimately becomes the same character that \(b_j\) ends up as.”
3. Batch conversion of strings: After processing all operations, the correspondence table showing which character each character (a through z) is ultimately converted to is complete. Using Python’s str.translate method (along with str.maketrans), we can efficiently perform the replacement of entire strings based on this correspondence table.

Complexity

• Time complexity: \(O(Q + \sum |S_i|)\)
  • Processing operations in reverse takes \(O(Q)\), and converting the final strings takes \(O(\sum |S_i|)\). Letting the number of character types be \(C=26\), more precisely it is \(O(Q + \sum |S_i| + C)\).
• Space complexity: \(O(\sum |S_i|)\)
  • Memory is needed to store the strings.

Implementation Notes

• Advantage of reverse processing: When processing from front to back, we would need to update the state of all 26 characters for each operation. However, processing from back to front requires only a single update per operation, making the implementation both simpler and more efficient.

• Fast I/O: Since \(N\), \(Q\), and the total length of strings can be large, we reduce Python execution time by reading all input at once with sys.stdin.read().split() and outputting all at once with sys.stdout.write.

• str.translate: Python’s built-in str.translate is implemented internally in C, making it far faster than replacing characters one by one in a loop.

  Source Code

import sys

def main():
    # 標準入力からすべてのトークンを一度に読み込みます。
    # これにより、大量の入力に対しても高速に処理を行うことができます。
    try:
        data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not data:
        return
        
    # N: ファイル（文字列）の数, Q: 置換操作の回数
    N = int(data[0])
    Q = int(data[1])
    
    # N個の文字列 S_1, ..., S_N を取得します。
    S = data[2:2+N]
    
    # 置換操作のクエリ (a_j, b_j) を取得します。
    # queries には 2*Q 個のトークンが含まれます。
    queries = data[2+N:2+N+2*Q]
    
    # 【アプローチの解説】
    # 既存の解法は「各操作ごとに26文字すべての現在の状態を更新する」という
    # 前方からのアプローチ（計算量 O(26*Q)）をとっています。
    # 本解法では、操作を「後ろから」処理することで、各文字が最終的に
    # どの文字に変換されるかを O(Q + 26) で決定します。
    # 
    # 合成関数 G_j を「操作 j から Q までを順番に適用した結果」とすると、
    # G_j(x) = G_{j+1}(f_j(x)) と表せます。ここで f_j は j 番目の置換 (a_j -> b_j) です。
    # つまり、文字 a_j は「その後の操作によって b_j が最終的になる文字」に変換されます。
    
    # mapping[i] は、文字 chr(97 + i) が最終的にどの文字になるかを保持します。
    # 最初は自分自身にマップされるように初期化します。
    mapping = [chr(i + 97) for i in range(26)]
    
    # 操作を逆順（Q-1 から 0 まで）に走査します。
    for i in range(Q - 1, -1, -1):
        # a_char: 置換元の文字, b_char: 置換先の文字
        a_char = queries[2 * i]
        b_char = queries[2 * i + 1]
        
        if a_char == b_char:
            continue
            
        # 文字 a_char は、現時点で b_char が最終的になるとされている文字へ更新されます。
        # ord('a') は 97 です。
        a_idx = ord(a_char) - 97
        b_idx = ord(b_char) - 97
        mapping[a_idx] = mapping[b_idx]
        
    # 最終的な変換マップを元に、高速な文字列置換のための変換テーブルを作成します。
    src_chars = "abcdefghijklmnopqrstuvwxyz"
    dst_chars = "".join(mapping)
    trans_table = str.maketrans(src_chars, dst_chars)
    
    # 各文字列に対して一括変換を適用します。
    # str.translate は内部が C で実装されており、非常に高速です。
    results = [s.translate(trans_table) for s in S]
    
    # すべての文字列を改行で結合して出力します。
    sys.stdout.write("\n".join(results) + "\n")

if __name__ == "__main__":
    main()

This editorial was generated by gemini-3-flash-preview.