Mô tả và yêu cầu

Trọng số xâu
Cho một xâu 𝑆 chỉ gồm các chữ cái tiếng Anh in thường. Trọng số của một xâu được
định nghĩa là: Tổng khoảng cách các ký tự trong xâu với kí tự đầu tiên của xâu đó (khoảng cách
giữa hai ký tự là giá trị tuyệt đối của hiệu hai ký tự đó).
Ví dụ, với xâu “cadc”, trọng số của xâu là:
|𝑐 – 𝑐| + |𝑎 – 𝑐| + |𝑑 – 𝑐| + |𝑐 – 𝑐| = 0 + 2 + 1 + 0 = 3
Yêu cầu: Hãy tìm một xâu con gồm các ký tự liên tiếp thuộc 𝑆 có trọng số lớn nhất và có ký tự
đầu trùng với ký tự cuối.
Dữ liệu vào từ tệp văn bản TSX.INP: Gồm một xâu ký tự có độ dài là 𝑁 (𝑁 ≤ 106).
Kết quả ghi ra tệp văn bản TSX.OUT: Một số nguyên là trọng số lớn nhất của xâu con thoả
mãn.

Ví dụ

TSX.INP                     TSX.OUT                                  Giải thích
 bcacadbac                    8                          Chọn đoạn con “cacadbac”
 abcaczc                      25                         Chọn đoạn con “caczc”
Ràng buộc:
       Có 50% số test ứng với 50% số điểm của bài thoả mãn: 𝑁                ≤  102;
       30% số test khác ứng với 30% số điểm của bài thoả mãn: 𝑁                ≤  104;
       20% số test còn lại ứng với 20% số điểm của bài không có ràng buộc gì thêm.