Chỉ Số Greenfield Tối Ưu Tải VNG

Mô tả

Tại trạm xử lý hạ tầng WebAssembly của VNG, hệ thống ghi lại một chuỗi nhật ký tải S gồm các ký tự chữ cái in hoa. Trong đó, ký tự 'G' đại diện cho một điểm nóng tải (Greenfield hotspot). Một đoạn nhật ký được xem là ổn định nếu không tồn tại hai ký tự 'G' nào đứng liền nhau.

Đội vận hành muốn thực hiện một phép biến đổi trên đoạn nhật ký: tại mỗi bước, chọn đúng một vị trí trong đoạn và thay ký tự tại đó bằng một ký tự in hoa bất kỳ khác 'G'. Mỗi vị trí chỉ được thay đổi nhiều nhất một lần. Hỏi với mỗi đoạn truy vấn từ vị trí l đến r, số bước biến đổi lớn nhất có thể thực hiện sao cho sau khi biến đổi, đoạn đó vẫn ổn định (không có 'GG' nào)?

Đầu vào

• S: chuỗi nhật ký, gồm các ký tự in hoa 'A'–'Z'.
• queries: mảng các cặp [l, r] với l <= r, chỉ số theo 0, đại diện cho đoạn S[l..r].

Đầu ra

• Trả về mảng số nguyên, phần tử thứ i là kết quả tương ứng với queries[i].

Ràng buộc

• 1 <= độ_dài(S) <= 10^5
• 1 <= số_lượng_truy_vấn <= 10^5
• 0 <= l <= r < độ_dài(S)

Ví dụ

Input: S = "GAGGGT", queries = [[0, 2], [0, 5], [2, 4]]

Output: [0, 1, 1]

Giải thích:

• Truy vấn [0, 2]: đoạn "GAG" không có 'G' liền nhau, ta đổi nhiều nhất 0 lần.
• Truy vấn [0, 5]: đoạn "GAGGGT" có đúng một cặp 'GG' (tại các chỉ số 3, 4). Ta đổi một trong hai ký tự 'G' thành ký tự khác, ví dụ thành "GAGXGT", thực hiện được 1 bước.
• Truy vấn [2, 4]: đoạn "GGG" có hai cặp 'GG' liền nhau tại (2,3) và (3,4). Ta đổi ký tự ở giữa (chỉ số 3) thành 'X' rồi đổi một trong hai ký tự đầu/cuối, ví dụ thành "GXG", thực hiện được 2 bước. Nhưng chờ đã, ta cần tìm số bước lớn nhất. Đoạn gồm 3 ký tự, ta đổi cả 3 thành 'X', thực hiện được 3 bước, kết quả là 3. Xin sửa lại kết quả cho truy vấn [2, 4] là 3. Như vậy, kết quả tổng thể là [0, 1, 3].