Sinh mọi mã ký tự khác nhau

Bối cảnh và bài toán

Một hệ thống thử nghiệm cần liệt kê mọi mã khác nhau có thể tạo bằng cách hoán vị toàn bộ ký tự của một chuỗi. Một số ký tự có thể trùng nhau, vì vậy hai cách đổi chỗ khác nhau nhưng tạo cùng chuỗi chỉ được tính một lần.

Yêu cầu

In số mã khác nhau và liệt kê chúng theo thứ tự từ điển tăng dần.

Input

• Một dòng chứa chuỗi chữ thường s.

Output

Dòng đầu là số lượng mã. Các dòng sau là từng mã theo thứ tự từ điển.

Ràng buộc

• 1 <= |s| <= 8
• s chỉ gồm a..z

Chấm điểm

Ví dụ 1

Input

aab

Output

3
aab
aba
baa

Giải thích. Có đúng ba hoán vị khác nhau vì hai ký tự a giống nhau.

Ví dụ 2

Input

ab

Output

2
ab
ba

Giải thích. Hai ký tự khác nhau tạo hai hoán vị.

Thông tin bài tập

Nguồn: Phỏng theo CSES Problem Set — Creating Strings (Task 1622).

Tham khảo: https://cses.fi/problemset/task/1622/