Nhỏ nhất theo thứ tự từ điển
Đề bài
Mô tả
Là một người cầu toàn, Hạnh bị ám ảnh bởi việc sắp xếp và sắp xếp lại mọi thứ. Khi các đồ vật không được bày biện theo cách "đúng", Hạnh thường cảm thấy khó chịu và thiếu trọn vẹn. Chẳng hạn, Hạnh rất bứt rứt khi nhìn thấy một đoạn code C++ có dấu ngoặc nhọn nằm trên một dòng riêng.
Hôm nay Hạnh nhận được một xâu dài vô tận. Xâu này trông thật tệ: nó có một số xâu con liên tiếp gồm các ký tự giống nhau, và thậm chí nó còn không nhỏ nhất theo thứ tự từ điển! Thật kinh khủng!! Hãy giúp Hạnh sắp xếp lại xâu.
Một cách hình thức, cho xâu và số nguyên . Bạn phải tìm một hoán vị của xâu sao cho:
- Trong không có xâu con độ dài nào mà mọi ký tự đều giống nhau.
- Trong tất cả các xâu thỏa mãn điều kiện trên, là xâu nhỏ nhất theo thứ tự từ điển.
Xâu là xâu con của xâu nếu có thể thu được bằng cách xóa một số (có thể là không hoặc tất cả) ký tự ở đầu và một số (có thể là không hoặc tất cả) ký tự ở cuối của . Ví dụ, abc là xâu con của abcd, nhưng abd thì không.
Xâu nhỏ hơn xâu theo thứ tự từ điển khi và chỉ khi một trong hai điều sau đúng:
- là tiền tố của và ;
- ở vị trí đầu tiên mà và khác nhau, ký tự của đứng trước ký tự tương ứng của trong bảng chữ cái.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên dương , số bộ test. Tiếp theo là bộ test, mỗi bộ test gồm dòng:
- Dòng thứ nhất chứa xâu khác rỗng, chỉ gồm các chữ cái tiếng Anh in thường.
- Dòng thứ hai chứa số nguyên dương .
Dữ liệu ra
Với mỗi bộ test, in ra trên một dòng xâu . Nếu không có đáp án, in ra một dòng chứa xâu OH NO!.
Ràng buộc
- Tổng độ dài các xâu không vượt quá .
- Tổng các giá trị không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 aabbccdd 2 aaa 2 |
ababcdcd OH NO! |
Với , không được có hai ký tự giống nhau đứng liền nhau. Xâu aaa không thể sắp xếp để thỏa mãn điều này. |
| 2 aaaab 3 abc 1 |
aabaa OH NO! |
Với , không được có ba chữ a liên tiếp. Với , mọi ký tự đều tạo thành một xâu con độ dài gồm các ký tự giống nhau, nên không có đáp án. |
Bình luận