Time Limit Exceeded for CodeChef Easy problem - STRQ (Chef and Strings)
Here is an efficient algorithm that requires O(n) time for initialization and O(1) time per query. 


Let's fix a pair (start letter, end letter)(there are only 12 such combinations). 
Now we can precompute the following value: count(len) - the number of strings that start with the start letter, end with the end letter and are located inside the prefix of length len. Here is a pseudo that does it:

for start_letter &lt;- letters:
    for end_letter &lt;- letters:
        if start_letter != end_letter:
            start_letter_count = 0
            strings_count = 0
            for i &lt;- 0 ... s.lenght() - 1:
                if s[i] == start_letter:
                    start_letters_count++
                else if s[i] == end_letter:
                    strings_count += start_letters_count
                count(i, start_letter, end_letter) = strings_count

The answer to a (left, right, start_letter, end_letter) is
count(right, start_letter, end_letter) - count(left - 1, start_letter, end_letter) - count_letter(left, right, end_letter) * count_letter(0, left - 1, start_letter), where count_letter(left, right, c) is the number of occurrences of a char c between left and right inclusively(it can be done in O(1) time with O(n) preprocessing using prefix sums).  Why does this formula work?
We can take all string that end before right. Now we need to subtract the number of strings that end before left. We also should subtract the number of such strings that start before left but end between left and right. 


The time complexity is O(n + q) because we traverse the given string once for each pair of start and end letters, and then we use one formula that is computed in O(1) to answer each query.