P16455 [UOI 2026] Unique Letters

给定两个由小写拉丁字母组成的字符串 $s$ 和 $t$。 你可以任意排列字符串 $s$ 中的字符，也可以任意排列字符串 $t$ 中的字符。 我们定义字符串 $x$ 的 **唯一化** 过程如下：首先，令辅助字符串 $a$ 为空。然后从左到右依次处理字符串 $x$ 中的字符。设当前字符为 $c$。 - 若字符 $c$ 未在当前字符串 $a$ 中出现，则将该字符 $c$ 追加到 $a$ 的末尾。 - 若字符 $c$ 已经在当前字符串 $a$ 中出现过，则将 $a$ 中从开头到**第一次**出现 $c$ 为止（包含该 $c$）的后缀从 $a$ 中删除。此时，当前正在处理的字符 $c$ 不会被加入。 将处理完所有字符后得到的字符串 $a$ 称为该字符串的 **唯一化** 结果。 请你判断是否能够通过排列得到字符串 $s'$ 与 $t'$，使得： - $s'$ 是字符串 $s$ 中字符的一个排列； - $t'$ 是字符串 $t$ 中字符的一个排列； - 字符串 $s'$ 的 **唯一化** 结果等于 $t'$。

第一行包含字符串 $s$ $(1 \le |s| \le 2 \cdot 10^5)$。 第二行包含字符串 $t$ $(1 \le |t| \le 2 \cdot 10^5)$。 两个字符串均仅由小写拉丁字母组成。

若无法得到满足要求的字符串 $s'$ 与 $t'$，输出 `NO`。 否则，输出 `YES`。接下来输出两行，分别为字符串 $s'$ 与 $t'$，满足： - $s'$ 是字符串 $s$ 中字符的一个排列； - $t'$ 是字符串 $t$ 中字符的一个排列； - 字符串 $s'$ 的 **唯一化** 结果等于 $t'$。

对于第一个样例： 我们将字符串 $s$ 排列为 `bcdbef`，将字符串 $t$ 排列为 `ef`。 构造字符串 $a$ 的过程如下： - 处理字符 `b` 后，$a = \texttt{b}$； - 处理字符 `c` 后，$a = \texttt{bc}$； - 处理字符 `d` 后，$a = \texttt{bcd}$； - 处理字符 `b` 时，字母 `b` 已在 $a$ 中存在，因此我们将 $a$ 中到第一次出现 `b` 为止的后缀删除。随后，$a$ 变为空字符串； - 处理字符 `e` 后，$a = \texttt{e}$； - 处理字符 `f` 后，$a = \texttt{ef}$。 在第四步中，字母 `c` 和 `d` 也一同从 $a$ 中被移除，而不仅仅是字母 `b`。 最终得到的字符串 $a$ 等于排列后的字符串 $t$，因此存在答案。 对于第二个样例： 我们将字符串 $s$ 排列为 `bcdbfbb`，并保持字符串 $t$ 为 `f`。 构造字符串 $a$ 的过程如下： - 处理字符 `b` 后，$a = \texttt{b}$； - 处理字符 `c` 后，$a = \texttt{bc}$； - 处理字符 `d` 后，$a = \texttt{bcd}$； - 处理字符 `b` 时，字母 `b` 已在 $a$ 中存在，因此我们将 $a$ 中到第一次出现 `b` 为止的后缀删除。随后，$a$ 变为空字符串； - 处理字符 `f` 后，$a = \texttt{f}$； - 处理字符 `b` 后，$a = \texttt{fb}$； - 处理字符 `b` 时，字母 `b` 已在 $a$ 中存在，因此我们将 $a$ 中到第一次出现 `b` 为止的后缀删除。随后，$a = \texttt{f}$。 在第四步中，字母 `c` 和 `d` 也一同从 $a$ 中被移除，而不仅仅是字母 `b`。 最终得到的字符串 $a$ 等于排列后的字符串 $t$，因此存在答案。 在第三个样例中，可以证明：对于字符串 `cgbfedc` 的任何排列，其 **唯一化** 结果都不可能是字符串 `gfbc` 的排列。 ### 计分 - （$4$ 分）：$|s|=|t|=1$； - （$8$ 分）：$s$ 可以通过排列字母得到 $t$； - （$8$ 分）：$s$ 中所有字母互不相同； - （$12$ 分）：字符串 $s$ 中仅有一个字母出现次数超过 $1$； - （$24$ 分）：$s=\texttt{aaaaabbbbbcccccddddd}$； - （$16$ 分）：$|s| \le 8$； - （$28$ 分）：无额外限制。 翻译由 DeepSeek V4 Pro 完成