Loading...
Loading...
Loading...
Riya has a long row of letter tiles from a word game, laid out in a fixed order. She wants to cut out one piece of consecutive tiles that contains every letter needed to spell her friend's name. A letter that appears twice in the name must appear at least twice in the piece. Extra tiles in the piece are allowed.
Print the shortest such piece. If there are several shortest pieces, print the one that starts first. If no piece works, print -1.
-1.Example 1
Input
xaybzcxabc abc
Output
abc
Both bzcxa and abc contain a, b and c. abc is the shortest.
Example 2
Input
aab aaa
Output
-1
The name needs three a tiles, but the row has only two.
Try the problem first. Open one hint at a time.
Count how many of each letter the name needs, and keep a number missing = tiles still missing from the piece.
Move right forward. If the new tile is a letter that is still needed, missing goes down by 1.
When missing is 0, the piece is valid. Record it, then move left forward to make it shorter, until a needed letter is lost.
Record a piece only when it is strictly shorter than the best so far. Then the first shortest piece is the one kept.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor