問題概要

一般に、文字列 $S$ からいくつかの文字を抜き出して、それを並び替えることによって文字列 $T$ を作れるとき、 $S$ から $T$ を作れるという。

英小文字からなる $N$ 個の文字列 $S_{1}, S_{2}, \dots, S_{N}$ が与えられる。

$S_{1}, S_{2}, \dots, S_{N}$ のいずれからも作れる文字列 $T$ のうち、最長のものを求めよ。複数考えられる場合は、そのうちの辞書順最小のものを求めよ。

制約

$1 \le N \le 50$
$1 \le |S_{i}| \le 50$

考えたこと

まずは、最長の長さを考えよう！

注目したいことは、各アルファベット文字ごとに独立に考えて良いということだ。つまり、

$T$ が文字 'a' を最大で何個含むことができるか
$T$ が文字 'b' を最大で何個含むことができるか
...
$T$ が文字 'z' を最大で何個含むことができるか

については、それぞれ独立に考えて良いのだ。そして、文字列 $T$ が含む文字 'a' の最大個数は

$S_{1}$ に含まれる 'a' の個数
$S_{2}$ に含まれる 'a' の個数
...
$S_{N}$ に含まれる 'a' の個数

の最小値を求めれば良い。

こうして、 $T$ の最長長さはわかった。最長である $T$ のうち、辞書順最小のものを求めるためには、単純に文字 'a' を並べて、次の文字 'b' を並べて......とすればよい。

計算量は、 $S_{1}, S_{2}, \dots, S_{N}$ に含まれる各文字の個数をバケットを用いて集計することで、 $O(CA)$ ( $C$ はアルファベット文字の個数、 $A = \sum_{i=1}^{N}|S_{i}|$ ) と評価できる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<string> S(N);
    for (int i = 0; i < N; i++) cin >> S[i];

    // S[0], ..., に a, b, ..., がそれぞれ何文字ずつあるかを計算する
    vector<vector<int>> nums(N, vector<int>(26, 0));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < S[i].size(); j++) nums[i][S[i][j] - 'a']++;
    }

    // a, b, ... について、S[0], ..., 内部での登場回数の最小値を求める
    string res;
    for (int i = 0; i < 26; i++) {
        int mi = nums[0][i];
        for (int j = 0; j < N; j++) mi = min(mi, nums[j][i]);
        res += string(mi, 'a' + i);
    }
    cout << res << endl;
}