Evolution Number of Characters
Xét một xâu S chỉ chứa các kí tự từ 'a'->'z' được mã hóa thành xâu SE (chỉ gồm các kí tự từ 'a'->'z' và kí tự từ '0'->'9') như sau: Đi từ trái qua phải, mã hóa dãy các kí tự liên tiếp bằng nhau trong S thành kí tự đại diện và số lượng kí tự đó. Ví dụ : "bbaaa" được mã hóa thành "b2a3".
Yêu cầu: Cho trước một xâu S đã được mã hóa và 2 số nguyên không âm L,R. Tính xem số lượng loại kí tự xuất hiện từ vị trí L -> R trên xâu S trước khi mã hóa là bao nhiêu. (Điều kiện đầu vào đảm bảo xâu S trước khi mã hóa có độ dài không quá 1015 kí tự và L,R đều bé hơn độ dài xâu S trước khi mã hóa)
Ví dụ:
- Với
S = "a3b4a10z1", L = 2, R = 15thìnumCharacters(S)= 2
Giải thích: XâuStrước khi được mã hóa là “aaabbbbaaaaaaaaaaz“. Nên xâu từ vị trí2đến vị trí15sẽ là"abbbbaaaaaaaa". Có2loại kí tự'a'và'b'xuất hiện trong xâu trên nên kết quả sẽ là2.
Đầu ra/Đầu vào
- [Giới hạn thời gian chạy] 0.5s với C++, 3s với Java/C#, 4s với Python,Js, Go
- [Đầu vào] string S
1 <= S.length() <= 106 - [Đầu vào] long L
0 <= L <= 1015 - [Đầu vào] long R
L <= R <= 1015 [Đầu ra] integer
Kết quả của bài toán
Post Comment