問題一覧 > 通常問題

No.1192 Half Subsequence

レベル : / AI推定難易度 : 1825 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 50
作問者 : 👑 Forested / テスター : define
お気に入りにしたユーザー ProblemId : 4848 / 自分の提出
問題文最終更新日: 2020-08-19 22:31:47
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
技術室奥プログラミングコンテスト#5 Day1 (順位表) の他の問題:

Problem Statement

A string $Y$ is called a subsequence of a string $X$ if and only if $Y$ can be obtained by removing $0$ or more characters from $X$ and concatenating the remaining characters without changing their order. For example, “aen”, “paken”, and “” (the empty string) are subsequences of “paken”, but “ne” and “aaa” are not subsequences of “paken”.

Given a string $S$ and a string $T$, find the lexicographically smallest string among those that are subsequences of $S$ but not subsequences of $T$. If no such string exists, answer $-1$.

Input

$S$
$T$
The string $S$ is given on line $1$.
The string $T$ is given on line $2$.

Output

Output the answer on $1$ line, followed by a newline.

Constraints

・ $1 \le |S|, |T| \le 100000$
・ Both $S$ and $T$ consist only of lowercase English letters

Sample

Sample 1
Input
abc
cacb
Output
abc

The strings that are subsequences of "abc" but not subsequences of "cacb" are "bc" and "abc". The lexicographically smallest of these is "abc", so the answer is "abc".

Sample 2
Input
paken
ppaakkeenn
Output
-1

No string is a subsequence of "paken" but not a subsequence of "ppaakkeenn", so the answer is $-1$.

Sample 3
Input
ba
ab
Output
ba

The only string that is a subsequence of "ba" but not a subsequence of "ab" is "ba".

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