| Submit | All submissions | Best solutions | Back to list |
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.
| 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 |
hide comments
|
2018-10-25 02:02:49 :D
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. |
|
|
2017-11-05 15:22:15
why in second input abcdy cannot be the answer?? |
|
|
2017-03-24 17:50:55 anonymous
It should be lexicographically smallest solution before sorting or after sorting? |
|
|
2017-02-05 18:27:15 abdou_93
@author can you check my submission id (18705906) RE: check for corner cases , u missing something!! Last edit: 2017-02-05 18:42:13 |
|
|
2017-02-02 20:26:39 wisfaq
aabbc is not a set but a multiset: https://en.wikipedia.org/wiki/Multiset So the answer for the problem is not a set but a multiset. RE: Thanks:) You should make it a "submultiset" Last edit: 2017-02-03 20:30:52 |
|
|
2017-02-02 18:45:16 Vipul Srivastava
can you please give me an example where its not happening? RE : its sorted now , look for bug in your program:) Last edit: 2017-02-02 19:05:34 |
|
|
2017-02-02 18:30:27 Vipul Srivastava
@author can you please check if submission and point me to where I am going wrong? RE: u have to output sorted subset; Last edit: 2017-02-02 18:41:21 |
|
|
2017-02-02 11:15:02
awesome... amazing!!!!! |
RSS