問題一覧 > 通常問題

No.3626 Not a Prefix

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 25
作問者 : 👑 loop0919 / テスター : ぽえ
ProblemId : 13771 / yukicoder contest 509 (順位表) / 自分の提出
問題文最終更新日: 2026-08-17 21:46:40
yukicoder contest 509の他の問題:

問題文

英小文字からなる空でない文字列が $N$ 個与えられます。$i ~ (1 \leq i \leq N)$ 番目の文字列は $S_i$ です。

あなたはこれらの文字列から $M$ 個自由に選ぶことができます。選んだ文字列はそれぞれ $T_1, T_2. \cdots, T_M$ とします。

以下の条件をすべて満たす文字列 $X$ が存在するような選び方が存在するか判定してください。そのような選び方存在する場合は、$X$ としてあり得る辞書順最小の文字列を出力してください。

  • $X$ は英小文字からなる空でない文字列である。
  • 任意の $k ~ (1 \leq k \leq M)$ について、 $X$ は $T_k$ の接頭辞でない
  • 任意の $k ~ (1 \leq k \leq M)$ について、 $T_k$ は $X$ の接頭辞でない

制約

  • $N, M$ は整数
  • $1 \leq M \leq N \leq 2 \times 10^5$
  • $S_i$ は英小文字からなる空でない文字列
  • $S_1, S_2, \cdots, S_N$ の長さの総和は $5 \times 10^5$ 以下

入力

各テストケースは以下の形式で与えられる。

$N$ $M$
$S_1$
$S_2$
$\vdots$
$S_N$

出力

条件を満たす選び方が存在するならば Yes 、そうでないならば No を出力せよ。
存在する場合、改行した後 $X$ としてあり得る辞書順最小の文字列を出力せよ。

サンプル

サンプル1
入力
5 2
apple
apricot
banana
cat
dog
出力
Yes
a

例えば $T_1, T_2$ として banana, cat を選ぶことで、$X =$ a が条件を満たします。

サンプル2
入力
26 26
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
z
出力
No

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。