If you naively scan \(S_{l_i}S_{l_i+1}\ldots S_{r_i}\) for each query to count the occurrences of the same alphabets, each query costs at worst \(\Theta(N)\) time, for a total of at worst \(\Theta(QN)\) time for the \(Q\) queries, so it is very unlikely that it finishes in the execution time limit.

We consider a faster way to respond to each query. Supposing a substring \(S_{l}S_{l+1}\ldots S_{r}\) is given in a query, let us consider how to find the answer it.

Based on the given string \(S\), define a sequence \(A = (A_1, A_2, \ldots, A_{N-1})\) of length \((N-1)\) by

\[A_i = \begin{cases} 1 &\text{if} \,\,S_i = S_{i+1}\\ 0 &\text{if}\,\, S_i \neq S_{i+1}. \end{cases}\]

Then the answer can be represented as \(A_{l} + A_{l+1} + \cdots + A_{r-1}\). Moreover, we define a sequence \(B = (B_0, B_1, B_2, \ldots, B_{N-1})\) by

\[B_i = \begin{cases} 0 &\text{if} \,\,i = 0\\ A_1 + A_2 + \cdots + A_i &\text{if}\,\, i \geq 1. \end{cases}\]

Here, \(B\) is the cumulative sum array of \(A\). Then, the answer to the query \(A_{l} + A_{l+1} + \cdots + A_{r-1} \) equals

\[A_{l} + A_{l+1} + \cdots + A_{r-1} = (A_1 + A_2 + \cdots + A_{r-1}) - (A_1 + A_2 + \cdots + A_{l-1}) = B_{r-1} - B_{l-1},\]

which is the difference of two elements of \(B\): \(B_{r-1} - B_{l-1}\). Therefore, if we compute the \(B\) firsthand, the answer to each query can be obtained in \(O(1)\) time just by evaluating \(B_{r-1} - B_{l-1}\).

Hence, the problem can be solved in a total of \(O(N+Q)\) time by

• first computing the sequence \(A\) and its cumulative sum array \(B\) against the string \(B\) given as the input;
• and then finding the answer \(B_{r_i-1} - B_{l_i-1}\) to each query in an \(O(1)\) time per query.

Note that one can compute the sequence \(B\) from the sequence \(A\) in a total of \(O(N)\) time by the recurrence relation of \(A\):

\[B_i = \begin{cases} 0 &\text{if} \,\,i = 0\\ B_{i-1} + A_i &\text{if}\,\, i \geq 1. \end{cases}\]

The following is sample code of this problem in C++ language.

#include <iostream>
using namespace std;

int n, q;
char s[300001];
int a[300000], b[300000];

int main(void)
{
  cin >> n >> q;
  for(int i = 1; i <= n; i++) cin >> s[i];
  
  for(int i = 1; i <= n-1; i++) if(s[i] == s[i+1]) a[i] = 1;
  for(int i = 1; i <= n-1; i++) b[i] = b[i-1] + a[i];
  
  int l, r;
  for(int i = 1; i <= q; i++){
    cin >> l >> r;
    cout << b[r-1]-b[l-1] << "\n";
  }
  
  return 0;
}