Overview

This problem asks you to simulate the process of inserting characters of a given string \(S\) one by one from left to right into a test tube, removing both characters only when the top character of the test tube and the newly inserted character form a pair found in the reaction table. By treating the test tube as a stack (with the top at the end), we can implement this directly.

Analysis

The two key observations are:

• For each reaction check, we only need two characters: the “current top” and the “character being inserted.”
• At most one reaction occurs per insertion (there are no chain reactions).

Because of this, there is no need to re-examine the entire test tube each time. A naive implementation using string concatenation or deletion could result in \(O(N)\) per operation, leading to \(O(N^2)\) overall (which is dangerous since \(N=10^6\)).

Instead, we manage the test tube as a stack (in Python, using append/pop on a list).

• When inserting character \(ch\):
  • If the stack is non-empty and (stack[-1], ch) is a reaction, then pop (both characters are eliminated).
  • Otherwise, append(ch).

Performing this for every character in \(S\) exactly matches the procedure described in the problem.

To further speed up reaction pattern lookup, we create a boolean table react[26][26] using the 26 uppercase English letters, making each check \(O(1)\).

For example, if (A, B) is a reaction, we set react[0][1] = True, and during checking we simply look up react[ord(top)-65][ord(ch)-65].

Algorithm

1. Read \(N, M\) and string \(S\).
2. Initialize react[26][26] to False.
3. For each reaction pattern \((X, Y)\), set react[X][Y] = True (converting characters to 0–25).
4. Prepare an empty stack stack.
5. Iterate through \(S\) from left to right, and for each character ch:
   • If stack is non-empty and react[top][ch] == True, then stack.pop().
   • Otherwise, stack.append(ch).
6. At the end, if stack is empty, output EMPTY; otherwise, output "".join(stack).

Complexity

• Time complexity: \(O(N + M)\) (Each character is pushed at most once and popped at most once; reaction checks take constant time.)
• Space complexity: \(O(N + 26^2)\) (The stack holds at most \(N\) elements; the reaction table is constant size.)

Implementation Notes

• Reactions are directional, so react[x][y] and react[y][x] are distinct.

• As stated in the problem, no chain reactions occur from a single insertion. The if ... pop else append logic accurately reproduces this behavior.

• For speed, it is recommended to use sys.stdin.readline for input.

• If the stack is empty at the end, be sure to output EMPTY.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    S = input().strip()

    react = [[False] * 26 for _ in range(26)]
    for _ in range(M):
        x, y = input().split()
        react[ord(x) - 65][ord(y) - 65] = True

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

    if stack:
        print("".join(stack))
    else:
        print("EMPTY")

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.3-codex.