Subtask 1, 2: ~N \le 2000~:

Ta sẽ duy trì ba biến ~bestL~, ~bestR~, ~bestCnt~ lần lượt là cặp ~L, R~ tối ưu nhất đang có gắn với giá trị ~bestCnt~ nhỏ nhất cần tìm.

Khi đó ta sẽ cố định một đầu ~L~ và for trâu đề tính các con ~R~ rồi tối ưu vào ba biến kết quả.

ĐPT: ~O~ ~(n^2)~.

Subtask 3: ~N \le 10^5~:

Quan sát có thể thấy chỉ có ~26~ ký tự tối đa do đó thực tế ta có thể tối ưu từ thuật toán trâu ở trên.

Duy trì một mảng ~last_c~ là vị trí cuối cùng mà ký tự ~c~ xuất hiện, vậy thay vì cố định con ~L~ như ở trên, ta sẽ cố định các con ~R~ với mỗi vị trí ~R~ ta sẽ duyệt lại các vị trí ~last~ của các ký tự và tối ưu lại đáp án như ở trên.

Độ phức tạp: ~O~ (~n \times 26~).

Code mẫu:

1

code vào đây