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: 4 = "aabb" 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.