📝 题目大意

给定 $n$ 个字符串，要求找出一个最长的字符串，使得该字符串能通过重新排列任意一个 $S_i$ 中的字符得到。若有多个最长字符串，输出字典序最小的。如果只有空串满足条件，输出空行。

💡 解题思路

1. 题目分析：题目本质上是在求所有 $n$ 个字符串的公共字符多重集的最大可能字符串。由于可以任意重排，字符顺序不重要，只关心每个字符的可用数量。将问题转化为：对于每个小写字母 $c$，它在答案中最多能出现多少次？显然，答案中 $c$ 的出现次数不能超过任意一个 $S_i$ 中 $c$ 的出现次数，即 $c$ 的可用次数等于所有串中 $c$ 出现次数的最小值。

2. 算法推导：

   • 朴素想法：枚举所有可能的子串/子序列？不可行，$|S_i| \leq 50$ 但组合数太多。
   • 关键洞察：字符之间独立——字母 a 能放多少个和字母 b 能放多少个互不影响。因此可以按字符独立统计。
   • 具体做法：用一个二维数组 a[i][c] 记录第 $i$ 个字符串中字符 $c$（$c \in [0, 25]$，对应 a~z）的出现次数。然后对每个字符 $c$，取所有 $n$ 个串中该字符出现次数的最小值，记作 b[c]。答案就是把字符 $\texttt{a}$ 重复 b[0] 次、字符 $\texttt{b}$ 重复 b[1] 次……字符 $\texttt{z}$ 重复 b[25] 次，依次拼接。
   • 为什么字典序最小？因为我们按 a 到 z 的顺序输出，所有 a 放在最前面，自然保证了字典序最小（任何其他排列都会在某个位置出现更大的字符）。

3. 边界与细节：

   • b[i] 初始化为一个充分大的数（代码中为 325125），确保 min 运算正确。注意 $n \leq 50$，$|S_i| \leq 50$，所以每个字符最多出现 50 次，325125 足够了。
   • 若所有字符的 b[i] 均为 0，则不会输出任何字符，即输出空行，符合题意。
   • 字符转数字索引：s[i][j] - 'a'，输出时反向转换：(char)('a' + i)。
   • 数据范围 $n \leq 50$，$|S_i| \leq 50$，所以 $O(26 \times n \times |S|)$ 非常轻松。

⏱️ 复杂度分析

• 时间复杂度：统计每个字符串的字符频率需要 $O(n \times |S_i|)$，最坏 $O(50 \times 50) = 2500$ 次操作。求每个字符的最小值需要 $O(26 \times n)$，输出需要 $O(\sum b[i]) \leq O(26 \times 50)$。总复杂度 $O(n \cdot |S_i|)$，即 $O(N \cdot L)$。
• 空间复杂度：a[59][59] 和 b[59] 均为常数大小，$O(1)$ 额外空间（不计输入字符串存储）。

💻 标准代码 (C++)

#include<bits/stdc++.h>
using namespace std;
long long n, a[59][59], b[59];  // a[i][c]: 第i个字符串中字符c的出现次数; b[c]: 字符c在所有串中的最小出现次数
string s[59];
int main()
{
	cin >> n;
	// 将每个字符的最小值初始化为一个足够大的数
	for (int i = 0; i <= 25; ++i)
	{
		b[i] = 325125;
	}
	// 读入每个字符串并统计字符频率
	for (int i = 1; i <= n; ++i)
	{
		cin >> s[i];
		for (int j = 0; j < s[i].size(); ++j)
		{
			++a[i][s[i][j] - 'a'];  // 将字符映射到 0~25
		}
	}
	// 对每个字符，取所有字符串中出现次数的最小值
	for (int i = 0; i <= 25; ++i)
	{
		for (int j = 1; j <= n; ++j)
		{
			if (a[j][i] < b[i])
			{
				b[i] = a[j][i];
			}
		}
		// 按 a~z 的顺序输出 b[i] 个该字符，保证字典序最小
		for (int j = 1; j <= b[i]; ++j)
		{
			cout << (char)('a' + i);
		}
	}
	return 0;
}