Question: Given an encoded String eg "a2bb3k11" that can be expended after decode "aabbbbbbkkkkkkkkkkk" and you have performe given range queries and find the length of the expended string;

input : a2bb3k11
3
0,3 = "a2bb"
2,5 = "bb3k"
2,6 = "bb3k1"
output: 2 = "aa"
6 = "bbbbbb"
7 = "bbbbbbk"

brute force will give (n*q) or (n^2) solution is there any way to optimize the queries to log(n) time.