CF1394C Boboniu and String

Boboniu 定义 BN-字符串为仅由字符 'B' 和 'N' 组成的字符串 $s$。 你可以对 BN-字符串 $s$ 执行以下操作： - 删除 $s$ 的一个字符。 - 删除 $s$ 的一个子串 "BN" 或 "NB"。 - 在 $s$ 的末尾添加一个字符 'B' 或 'N'。 - 在 $s$ 的末尾添加一个字符串 "BN" 或 "NB"。 注意，如果字符串 $a$ 可以通过从字符串 $b$ 的开头和结尾各删除若干（可以为零或全部）字符得到，则称 $a$ 是 $b$ 的子串。 Boboniu 认为，当且仅当满足以下条件时，BN-字符串 $s$ 和 $t$ 是相似的： - $|s|=|t|$。 - 存在一个排列 $p_1, p_2, \ldots, p_{|s|}$，使得对于所有 $i$（$1\le i\le |s|$），有 $s_{p_i}=t_i$。 Boboniu 还定义了 $ \text{dist}(s,t) $，即将 $s$ 变为与 $t$ 相似所需的最少操作次数。 现在，Boboniu 给你 $n$ 个非空 BN-字符串 $s_1,s_2,\ldots, s_n$，请你找到一个非空 BN-字符串 $t$，使得其与所有字符串 $s_i$ 的最大距离 $\max_{i=1}^n \text{dist}(s_i,t)$ 最小。也就是说，你需要最小化 $\max_{i=1}^n \text{dist}(s_i,t)$。

第一行包含一个整数 $n$（$1\le n\le 3\cdot 10^5$）。 接下来的 $n$ 行，每行包含一个字符串 $s_i$（$1\le |s_i| \le 5\cdot 10^5$）。保证每个 $s_i$ 只包含 'B' 和 'N'。所有字符串长度之和不超过 $5\cdot 10^5$。

第一行输出最小的 $\max_{i=1}^n \text{dist}(s_i,t)$。 第二行输出一个满足条件的 $t$。 如果有多个满足条件的 $t$，你可以输出任意一个。

在第一个样例中，$\text{dist(B,BN)}=\text{dist(N,BN)}=1$，$\text{dist(BN,BN)}=0$。所以最大距离为 $1$。 由 ChatGPT 4.1 翻译