No.1192 Half Subsequence
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
Forested