Overview

The state of the test tube \(T\) can be treated as a stack where “the end is the top,” so the problem reduces to reading characters from left to right and repeatedly “pushing / removing one element.”
Whether a reaction occurs depends only on two characters — “the current top character” and “the new character being added” — so it can be simulated with a stack.

Analysis

The key insight of this problem is that we only need to look at the top of the test tube each time.

When inserting a new character \(S_i\):

• If \(T\) is empty, simply push it
• Let \(c\) be the top of \(T\). If \((c, S_i)\) matches a reaction pattern:
  • Remove \(c\)
  • Do not insert \(S_i\) either
• Otherwise, push \(S_i\)

An important detail here is stated in the problem:

After an annihilation occurs, no further reaction check is performed against the newly exposed end of \(T\).

In other words, at most one reaction occurs per insertion.
There is no need to consider chain reactions.

Why a stack?

Since the end of the test tube corresponds to the top, the following operations occur frequently:

• Append to the end
• Remove from the end
• Look at the end

This is exactly what a stack does.

For example, suppose \(S = \texttt{ABCA}\) with reaction patterns \((A,B), (C,A)\):

1. Insert A → A
2. Insert B
   The top is A, and \((A,B)\) reacts → A and B are removed → empty
3. Insert C → C
4. Insert A
   The top is C, and \((C,A)\) reacts → empty

The result is empty.

Why naive approaches are problematic

1. Linear search through reaction patterns each time

If we check all \(M\) reaction patterns sequentially for each character insertion, the time complexity becomes \(O(NM)\).

Given the constraints:

• \(N \le 10^6\)
• \(M \le 676\)

In the worst case, approximately \(10^6 \times 676\) checks are needed, which is quite heavy.

2. Directly updating Python strings

Python strings are immutable, so performing

• Append to the end
• Remove from the end

by creating a new string each time can result in \(O(N^2)\) in the worst case.

How to solve it

• Manage the test tube \(T\) using a list-based stack
• Store reaction patterns in a \(26 \times 26\) boolean table for \(O(1)\) lookups

Since there are only 26 types of uppercase English letters,
setting react[x][y] = True if \((x, y)\) reacts allows for fast lookups.

This way, the processing for each character takes constant time, and the overall complexity is \(O(N + M)\).

Algorithm

1. Initialize react[26][26] with all False.
2. For each given reaction pattern \((X_k, Y_k)\), set react[X_k][Y_k] = True.
3. Prepare an empty stack stack.
4. Iterate through string \(S\) from left to right:
   • Let the current character be ch
   • If stack is not empty and
     react[top of stack][ch] == True:
     • Execute stack.pop()
     • Do not push ch
   • Otherwise:
     • Execute stack.append(ch)
5. At the end, if stack is empty, output EMPTY; otherwise, concatenate and output.

Complexity

• Time complexity: \(O(N + M)\)
• Space complexity: \(O(N + 26^2)\)

※ Since \(26^2 = 676\) is a constant, the space complexity is effectively \(O(N)\).

Implementation Notes

• Reaction patterns are directional. Even if \((X, Y)\) exists, \((Y, X)\) may not, so make sure to store them in the correct order.

• Converting uppercase letters to 0–25 with A as 0 makes it convenient to directly index into react.

• Since \(N\) can be large, input is read using sys.stdin.buffer.read() for speed.

• If the stack is empty at the end, make sure to output EMPTY rather than an empty string.

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    if not data:
        return

    n = int(data[0])
    m = int(data[1])
    s = data[2].decode()

    react = [[False] * 26 for _ in range(26)]
    idx = 3
    for _ in range(m):
        x = data[idx][0] - 65
        y = data[idx + 1][0] - 65
        react[x][y] = True
        idx += 2

    stack = []
    for ch in s:
        c = ord(ch) - 65
        if stack and react[ord(stack[-1]) - 65][c]:
            stack.pop()
        else:
            stack.append(ch)

    sys.stdout.write(''.join(stack) if stack else 'EMPTY')

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.