CF1085E Vasya and Templates

Vasya 拥有三个字符串 $s$、$a$ 和 $b$，它们都只包含前 $k$ 个拉丁字母。 我们定义“模板”为长度为 $k$ 的字符串，且每个前 $k$ 个拉丁字母在其中恰好出现一次（因此共有 $k!$ 种不同的模板）。将模板 $p$ 应用于字符串 $s$，即将 $s$ 中的每个字符 $c$ 替换为 $p_i$，其中 $i$ 是字母 $c$ 在字母表中的序号。例如，将模板 "bdca" 应用于字符串 "aabccd"，得到字符串 "bbdcca"。 Vasya 想知道，是否存在这样一个模板，使得将其应用于 $s$ 后得到的字符串，字典序不小于字符串 $a$，且不大于字符串 $b$。 如果存在多个满足条件的模板，输出任意一个即可。 若对于某个 $i$（$1 \le i \le n$），有 $a_i < b_i$，且对于所有 $j$（$1 \le j < i$），有 $a_j = b_j$，则称字符串 $a$ 的字典序小于字符串 $b$。 你需要独立地回答 $t$ 组测试数据。

第一行包含一个整数 $t$（$1 \le t \le 10^6$），表示测试数据组数。 在 hacks 中只能使用 $t = 1$。 接下来的每组测试数据包含如下内容： 每组测试数据的第一行包含一个整数 $k$（$1 \le k \le 26$），表示模板的长度。 第二行包含字符串 $s$（$1 \le |s| \le 10^6$）。 第三行包含字符串 $a$。 第四行包含字符串 $b$。 字符串 $s$、$a$ 和 $b$ 长度相同（$|s| = |a| = |b|$），且都只包含前 $k$ 个小写拉丁字母。 保证 $a$ 的字典序不大于 $b$。 保证所有测试数据中字符串的总长度不超过 $3 \cdot 10^6$。

对于每组测试数据，输出如下内容： 如果不存在满足条件的模板，第一行输出 "NO"。 否则，第一行输出 "YES"，第二行输出一个模板（$k$ 个小写字母，每个前 $k$ 个拉丁字母恰好出现一次）。 如果存在多个满足条件的模板，输出任意一个即可。

由 ChatGPT 4.1 翻译