問題一覧 > 通常問題

No.1192 半部分列

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 41
作問者 : ForestedForested / テスター : definedefine
9 ProblemId : 4848 / 出題時の順位表
問題文最終更新日: 2020-08-19 22:31:47

問題文

文字列 $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もしくは右上の雲マークをクリックしてアカウントを作成してください。