Cho một xâu s gồm các chữ cái thường. Hãy dùng toàn bộ ký tự của s đúng số lần xuất hiện để tạo ra tất cả các xâu khác nhau. Hai cách đổi chỗ các ký tự giống nhau vẫn chỉ tạo một kết quả. Danh sách kết quả phải theo thứ tự từ điển.
Input
Dòng duy nhất chứa xâu s.
Output
Dòng đầu in số lượng xâu khác nhau. Sau đó in mỗi xâu trên một dòng theo thứ tự từ điển.
Constraints
1≤∣s∣≤8.
Mỗi ký tự của s nằm trong 'a'..'z'.
Scoring
Subtask 1 (50%): ∣s∣≤5.
Subtask 2 (50%): Không có giới hạn bổ sung.
Example
Test 1
Input
aab
Output
3
aab
aba
baa
Giải thích: Ba hoán vị phân biệt là aab, aba, baa; đổi chỗ hai ký tự a không tạo thêm xâu mới.
Lời giải tóm tắt
Ý tưởng: Thay vì phân biệt các bản sao của cùng một chữ cái, lưu tần suất còn lại của 26 chữ. Ở mỗi vị trí, thử từng chữ từ a đến z có tần suất dương, giảm tần suất, đệ quy, rồi hoàn tác.
Ý tưởng: Số kết quả được tính trước bằng công thức đa thức n! / ∏ cnt[c]!, nhờ đó có thể in số lượng trước mà không cần lưu toàn bộ các xâu. Thứ tự thử chữ tăng dần tạo trực tiếp thứ tự từ điển.
Chứng minh tính đúng đắn: Mỗi bước chỉ lấy một ký tự còn trong đa tập, nên mọi lá dùng đúng số lần xuất hiện của từng chữ. Với một xâu đích, ký tự tại mỗi vị trí xác định duy nhất nhánh phải đi, vì các bản sao giống nhau được gộp bằng tần suất; do đó xâu ấy được sinh đúng một lần. Thuật toán thử mọi chữ còn lại ở mọi vị trí nên không bỏ sót hoán vị phân biệt nào. Công thức đếm chia n! cho số cách hoán đổi nội bộ các ký tự bằng nhau, đúng bằng số lá được sinh.
Độ phức tạp: Gọi K là số xâu phân biệt. Thời gian kể cả in là O(n·K) cộng chi phí thử 26 chữ ở các nút; bộ nhớ phụ O(n+26).