No.1192 半部分列
タグ : / 解いたユーザー数 50
作問者 :
Forested
/ テスター :
define
問題文
文字列 $X$ から $0$ 個以上の文字を取り除き、残った文字を順序を変えずにつなげることで文字列 $Y$ と一致させられるとき、またそのときに限り、文字列 $Y$ は文字列 $X$ の部分列であると呼びます。
例えば “aen” や “paken” 、 “” ( 空文字列 ) は “paken” の部分列ですが、 “ne” や “aaa” は “paken” の部分列ではありません。
文字列 $S$ と文字列 $T$ が与えられるので、 $S$ の部分列であり $T$ の部分列ではないような文字列のうち、辞書順最小のものを答えてください。ただし、そのような文字列が存在しない場合は $-1$ と答えてください。
入力
$S$ $T$$1$ 行目に、文字列 $S$ が与えられます。
$2$ 行目に、文字列 $T$ が与えられます。
出力
答えを $1$ 行に出力し、最後に改行をしてください。
制約
・ $1 \le |S|, |T| \le 100000$
・ $S$ と $T$ はともに英小文字のみからなる
サンプル
サンプル1
入力
abc cacb
出力
abc
"abc" の部分列であり "cacb" の部分列ではないような文字列として "bc" と "abc" が考えられます。このうち辞書順最小のものは "abc" なので、答えは "abc" です。
サンプル2
入力
paken ppaakkeenn
出力
-1
"paken" の部分列であり "ppaakkeenn" の部分列ではないような文字列は存在しないため、答えは $-1$ となります。
サンプル3
入力
ba ab
出力
ba
"ba" の部分列であり "ab" の部分列ではないような文字列は "ba" のみです。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。