思路概述

我们把“等价”理解为字符多重集合相同（即字母出现次数一致、顺序无关）。对每个字符串 $s_i$ ，只要它包含某个字母 $c$ 至少 $x$ 次，就能从中挑出 $x$ 个 $c$ 作为子序列的一部分。于是：

若要存在同一个字符串 $t$ 被每个 $s_i$ 的某个子序列“等价”，那么对每个字母 $c$ ，在 $t$ 中的出现次数 $\text{cnt}_t[c]$ 不能超过所有字符串中该字母出现次数的最小值：
$\text{cnt}_t[c] \le \min_i \text{cnt}_{s_i}[c]$

P4315.【哈希5】子序列

1000ms

Difficulty: 5

算法与标签>哈希表

本题为2025年8月31日得物机考原题

得物机考的介绍点击这里

定义两个字符串是等价的，当且仅当其中一个串可以通过重新排列这些字符得到另一个串。例如， $abccb$ 和 $cbcba$ 等价， $a$ 和 $a$ 等价， $abba$ 和 $baab$ 等价。而 $abc$ 和 $aac$ 不等价， $a$ 和 $b$ 不等价。

现在输入 $n$ 个仅由小写字母组成的字符串 $s_1,s_2,…,s_n$ ，你需要找到一个长度最长的字符串 $t$ ，使得每个串都能找到一个子序列，这个子序列形成的字符串与 $t$ 等价。

如果有多个答案，请输出字典序最小的串。如果找不到，则输出 $-1$ 。

第一行输入一个正整数 $T(1≤T≤5)$ ，表示数据组数。

对于每一组数据:

第一行输入一个正整数 $n(1≤n≤10^4)$ ，表示字符串的个数。

第二行输入 $n$ 个仅由小写字母组成的字符串 $s_1,s_2,...s_n$ ，每两个字符串之间用一个空格隔开，末尾没有多余空格。

保证同一组数据的字符串长度之和不超过 $10^5$ 。

对于每一组数据，输出一行。如果有多个答案，请输出字典序最小的串。如果找不到，则输出 $-1$ 。

输入

2
3
path photo hope
2
abc def

输出

hp
-1

输入

预期输出（选填）