# **Bài toán thứ tự từ điển của xâu**
Trong bài viết này, mình sẽ giới thiệu đến các bạn một bài toán kinh điển như sau:
> Cho một xâu kí tự s trong đó không có kí tự nào trùng nhau, hãy tìm thứ tự của nó trong dãy các hoán vị được sắp xếp tăng dần theo thứ tự từ điển.

Một xâu a được coi là có thứ tự từ điển thấp hơn xâu b nếu một trong những điều kiện sau đây thỏa mãn:
* Xâu a là tiền tố của xâu b, nhưng a ≠ b,
* Ở vị trí đầu tiên hai xâu khác nhau, chữ cái ở xâu a xuất hiện sớm hơn chữ cái tương ứng ở xâu b theo thứ tự bảng chữ cái.

# Ví dụ:
**Input:** s = "bac".
**Output:** 3
**Giải thích:** Nếu tất cả các hoán vị của xâu được sắp xếp theo thứ tự từ điển thì chúng sẽ là “abc”, “acb”, “bac”, “bca”, “cab”, “cba”. Từ đây có thể thấy rõ thứ tự của s là 3.

**Input:** s = "debac".
**Output:** 93.

# Thuật toán ngây thơ!!
Đối với cách này đơn giản ta chỉ cần duyệt qua tất cả các hoán vị của xâu và kiểm tra được thứ tự của xâu cần tìm.
**Độ phức tạp:** **O(n!)**, vì trong trường hợp xấu nhất ta phải duyệt qua n! hoán vị của xâu.
Dĩ nhiên, độ phức tạp này là quá lớn, ta phải tìm cách tối ưu nó:
# Thuật toán tối ưu
**Nhận xét:**
Đối với các ký tự trong mỗi vị trí, hãy tìm xem có thể tạo được bao nhiêu xâu có thứ tự từ điển bé hơn khi tất cả các ký tự từ đầu cho đến vị trí đó được cố định. Cộng dần vào kết quả ta có thứ tự cần tìm.
Để hiểu rõ hơn, ta sẽ xét ví dụ sau:
Xét xâu s = "debac", chữ cái "d" là kí tự ở vị trí thứ nhất. Có tất cả 5 chữ cái và 3 trong đó nhỏ hơn "d". Vì vậy ta có thể chọn được 3 * 4! xâu có thứ tự thấp hơn, gồm những dạng như sau:

- a x x x x
- b x x x x
- c x x x x

Tương tự ta có thể áp dụng quy tắc như trên cho các vị trí khác. Cố định "d" và tiếp tục tìm các xâu có thứ tự từ điển bé hơn bắt đầu bằng kí tự "d".

- Lặp lại thao tác như trên với "e", lưu ý rằng, vì "d" cố định rồi nên ta không xét đến nữa, kết quả sẽ là 3 * 4! + 3 * 3!
- Cố định "e" và lặp lại thao tác như trên với "b", kết quả sẽ là 3 * 4! + 3 * 3! + 1 * 2!
- Cố định "b" và lặp lại thao tác như trên với "a", kết quả sẽ là 3 * 4! + 3 * 3! + 1 * 2! + 0 * 1!
- Cố định "a" và lặp lại thao tác như trên với "c", kết quả sẽ là 3 * 4! + 3 * 3! + 1 * 2! + 0 * 1! + 0 * 0!
- Cố định "c", không thể tiếp tục thao tác được nữa, ta dừng việc thao tác ở đây.

Ta sẽ có tổng cộng 3 * 4! + 3 * 3! + 1 * 2! + 0 * 1! + 0 * 0! = 92 xâu có thứ tự từ điển thấp hơn "debac", vì vậy thứ tự từ điển của nó là 92 + 1 = 93.

**Cài đặt:**
1. Duyệt xâu s lần lượt từ trái qua phải theo từng vị trí:
- Đối với vị trí i, tìm số lượng j (j > i) sao cho s[i] > s[j]
- Nhân số lượng vừa tìm được với (n - i)! (số lượng cách chọn các kí tự còn lại sau khi đã cố định i phần tử đầu tiên)
2. Sau khi duyệt xong, cộng một vào kết quả, ta thu được thứ tự từ điển cần tìm.

**Code mẫu: Xem hình 1**
**Độ phức tạp: O(n^2)**

# Câu hỏi mở?
1. Có thể tối ưu thuật toán thêm nữa không?
2. Bài toán ngược: Cho thứ tự từ điển của một xâu, liệu ta có thể xây dựng được xâu đó?