Overview

This is a problem where character replacement operations are repeatedly performed on multiple strings. It is solved by efficiently tracking which character each character is ultimately converted to.

Analysis

Problems with the Naive Approach

The simplest method is to scan all strings and replace characters for each replacement operation.

However, with this approach: - The total length of all strings is at most \(10^6\) - There are at most \(10^5\) replacement operations

Therefore, in the worst case, \(10^6 \times 10^5 = 10^{11}\) operations would be needed, resulting in TLE (Time Limit Exceeded).

Key Insight

There are only 26 types of lowercase English letters.

Since each replacement operation is “change character \(a\) to character \(b\)”, it is sufficient to track only what each character ultimately becomes.

For example, consider the following operations: 1. a → b 2. b → c

In this case, a character that was originally a becomes b after operation 1, then becomes c after operation 2. A character that was originally b also becomes c after operation 2.

In other words, the final mapping is “a → c, b → c”.

Solution

1. Initially prepare a mapping where “each character maps to itself” (a→a, b→b, …)
2. For each replacement operation, update the mapping destination for all characters that are currently scheduled to be converted to that character
3. Finally, apply the mapping to all strings at once

Algorithm

1. Initialization: Create a mapping table for 26 characters (each character maps to itself)

   mapping = {'a': 'a', 'b': 'b', ..., 'z': 'z'}
   

2. Processing replacement operations: For each operation \((a_j, b_j)\)

   • Scan the entire mapping table
   • Update characters currently mapped to \(a_j\) so that they map to \(b_j\) instead

3. String conversion: After all operations are complete

   • Convert each string exactly once using the final mapping table

Complexity

• Time complexity: \(O(Q \times 26 + \sum|S_i|)\)

  • Checking the mapping of 26 characters for each replacement operation: \(O(26Q)\)
  • Converting all strings: \(O(\sum|S_i|)\)
  • Given the constraints \(Q \leq 10^5\) and \(\sum|S_i| \leq 10^6\), this is sufficiently fast

• Space complexity: \(O(\sum|S_i|)\)

  • Required for storing the input strings and output strings

Implementation Notes

1. Be careful with how the mapping is updated

   • For the operation “\(a\) → \(b\)”, change the mapping destination to \(b\) for all original characters whose current mapping destination is \(a\)
   • Simply doing mapping['a'] = 'b' is insufficient (it cannot track chained replacements)

2. Utilizing Python’s str.maketrans() and translate()

   • A translation table can be created from the mapping dictionary to efficiently convert strings
   • Conversion is completed in a single pass for each string

3. Speeding up input

   • Using sys.stdin.read() allows reading large amounts of input quickly

     Source Code

import sys

def main():
    input = sys.stdin.read().split('\n')
    idx = 0
    N, Q = map(int, input[idx].split())
    idx += 1
    
    strings = []
    for i in range(N):
        strings.append(input[idx])
        idx += 1
    
    # Create a mapping for each character
    # mapping[c] = the character that c will become after all operations
    mapping = {chr(ord('a') + i): chr(ord('a') + i) for i in range(26)}
    
    # Process all replacement operations
    for j in range(Q):
        a, b = input[idx].split()
        idx += 1
        # For every character that currently maps to 'a', change it to map to 'b'
        for c in mapping:
            if mapping[c] == a:
                mapping[c] = b
    
    # Build translation table
    trans_table = str.maketrans(mapping)
    
    # Apply the final mapping to all strings
    result = []
    for s in strings:
        result.append(s.translate(trans_table))
    
    print('\n'.join(result))

if __name__ == "__main__":
    main()

---

This editorial was generated by claude4.5opus.