Dãy con và hoán vị của xâu
Đề bài
Mô tả
Cho hai xâu và , hãy tìm xâu có thứ tự từ điển nhỏ nhất thỏa mãn đồng thời các điều kiện sau:
- là một dãy con của (nhận được bằng cách xóa đi một số ký tự của , có thể không xóa ký tự nào, và giữ nguyên thứ tự các ký tự còn lại).
- là một hoán vị của (nhận được bằng cách sắp xếp lại các ký tự của ).
Dữ liệu vào
- Dòng thứ nhất là xâu ().
- Dòng thứ hai là xâu ().
- Cả hai xâu chỉ gồm các chữ cái Latin in thường (từ a đến z).
Dữ liệu ra
In ra xâu thỏa mãn các điều kiện trên. Nếu không có xâu nào như vậy, in ra .
Ràng buộc
- , .
- và chỉ gồm chữ cái Latin in thường.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| bcadca dacb |
badc | Các dãy con của là hoán vị của là bcad, bcda, badc và bdca; nhỏ nhất là badc (lấy b, a, d, c ở các vị trí ). |
| icpccentral nccai |
iccna | Lấy i, c, c, n, a ở các vị trí . |
| uuuuuu uzt |
-1 | không có chữ z và chữ t. |
Bình luận