HARSTR - TWO STRINGS
You are given two strings a and b. You have to remove the minimum possible number of consecutive (standing one after another) characters from string b in such a way that it becomes a submultiset of string a. It can happen that you will not need to remove any characters at all, or maybe you will have to remove all of the characters from b and make it empty.
Input
The first line contains string a, and the second line contains string b. Both of these strings are non-empty and consist of lowercase letters of English alphabet. The length of each string is no bigger than 105 characters.
Output
On the first line output a submultiset of string a in sorted order, obtained from b. If multiple answers exist, output lexicographically smallest.
If the answer consists of zero characters, output "-" (a minus sign).
Example
Input: abacaba abcdcba Output: aabbc
Input: abcdy abdxybc Output: abcd
Note: ouput is abcd not abcy since abcd is lexicographically smaller.
hide comments
|
:D:
2018-10-25 02:02:49
re kush_pathak01: to get 'abcdy' from 'abdxybc' we need to remove 'x' and one 'b', so this means either 'bdx' or 'xyb' (we must remove consecutive characters). Either way we are left with 'abcy' or 'abcd'. 'abcdy' is not possible. |
|
kush_pathak01:
2017-11-05 15:22:15
why in second input abcdy cannot be the answer?? |
|
anonymous:
2017-03-24 17:50:55
It should be lexicographically smallest solution before sorting or after sorting? |
|
abdou_93:
2017-02-05 18:27:15
@author can you check my submission id (18705906)
|
|
wisfaq:
2017-02-02 20:26:39
aabbc is not a set but a multiset:
|
|
Vipul Srivastava:
2017-02-02 18:45:16
can you please give me an example where its not happening?
|
|
|
Vipul Srivastava:
2017-02-02 18:30:27
@author can you please check if submission and point me to where I am going wrong?
|
|
sanju04:
2017-02-02 11:15:02
awesome... amazing!!!!! |
| Added by: | har_vi |
| Date: | 2017-01-29 |
| Time limit: | 2s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 GOSU |
| Resource: | Codeforces , @nonushikhar |
RSS