D - Three Letters
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
英大文字および英小文字によって構成される N 個の文字列 A_1,A_2,...,A_N があります。
文字列の 略称 を以下のように定義します。
- 文字列 S があるとき、1 \leq i < j < k \leq |S| を満たす任意の i,j,k に対し、S_i S_j S_k は S の略称となる。
3 文字からなる文字列のうち、A_1,A_2,...,A_N のうち最も多くの文字列の略称となるものを求めてください。
ただし、複数ある場合は、辞書順で最初のものを求めてください。
なお、辞書順において、文字の種類にかかわらず英大文字は英小文字より必ず先になるとします。
制約
- 1 \leq N \leq 30000
- 3 \leq |A_i|
- |A_1|+|A_2|+...+|A_N| \leq 90000
- A_i は英大文字および英小文字からなる
入力
入力は以下の形式で標準入力から与えられる。
N A_1 : A_N
出力
3 文字からなる文字列のうち、A_1,A_2,...,A_N のうち最も多くの文字列の略称となるものを求めよ。
ただし、複数ある場合は、辞書順で最初のものを求めよ。
入力例 1
4 aKIHaBaRa aKIBa aSaKUSa SHINKIBA
出力例 1
KIB
3 つの文字列の略称となるものは KIB
,aKa
ですが、これらのうち辞書順で最初の KIB
を出力するとよいです。
辞書順において、英大文字は英小文字より必ず先になるので、K
がa
より先になることに注意してください。
入力例 2
3 abc def ghi
出力例 2
abc