Bài 3: Trò chơi xâu ký tự Bạn được cho một xâu ký tự gồm N ký tự. Đầu tiên, bạn được sắp xếp lại các ký tự trong xâu theo một thứ tự bất kỳ. Sau đó, hãy chia xâu ký tự này thành chính xác K xâu ký tự liên tiếp

Để giải bài toán này, chúng ta cần làm theo các bước sau:

1. Sắp xếp xâu ký tự: Bước đầu tiên là sắp xếp các ký tự trong xâu cho đến khi có được xâu ký tự theo thứ tự từ điển (muốn có từ điển lớn nhất nên ta sẽ sắp xếp các ký tự giảm dần).

2. Chia xâu thành K phần: Sau khi đã sắp xếp, mục tiêu là phân chia xâu ký tự thành K xâu liên tiếp sao cho có thứ tự từ điển lớn nhất. Để đạt được điều này, ta cần đảm bảo rằng các xâu con trong phân chia này là không rỗng.

3. Tìm cách chia tối ưu: Chia xâu thành K phần mà có thứ tự từ điển lớn nhất đồng nghĩa với việc ưu tiên để xâu cuối cùng có giá trị lớn nhất. Để thực hiện điều này, ta có thể sử dụng một thuật toán tham lam: chia từ cuối lên và tạo ra các phần tối ưu. Cụ thể, ta bắt đầu từ vị trí cuối của xâu ký tự đã sắp xếp và tìm cách chia nó thành K phần bằng cách chọn các ký tự một cách khéo léo.

Dưới đây là ví dụ cụ thể cho trường hợp `N = 4`, `K = 2`, và xâu `baba`:
- Sắp xếp các ký tự trong xâu thành `bbaa`.
- Khi phân chia xâu `bbaa` thành K = 2 phần, ta có thể tạo ra các cặp như:
1. `b` và `baa`
2. `ba` và `ba`
3. `b` và `ba`
4. `bb` và `a`

Chúng ta ưu tiên để phần sau lớn nhất theo thứ tự từ điển, do đó:
- Phân chia `ba` và `ba` có được thứ tự từ điển lớn nhất là `ba`.

Kết quả cho bài toán là chuỗi có thứ tự từ điển lớn nhất của phương án tối ưu là `ba`.