For a candidate range $(a,b)$, it suffices to compute the minimum number of strokes for the prefix of length $a-1$ and suffix of length $N-b$ independently and add them up. Now let's describe how to compute the minimum number of strokes for each prefix (suffixes are computed similarly).

There are a few ways to accomplish this. Perhaps the easiest is to scan the input from left to right while maintaining a stack of "active brush strokes". Every time we see a higher color than the one on top of the stack, we push it onto the stack (so the stack will contain ascending colors from bottom to top). Every time we see a color $c$, we pop from the stack every color larger than $c$, since those brush strokes need to be ended for color $c$ to be visible. The aggregate number of pushes onto the stack tells us the number of brush strokes required for each prefix. Here is Brian Dean's code that implements this idea, running in $O(N + Q)$ time:

#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;
const int MAX_N = 100000;
  
string S;
int N, prefix_sol[MAX_N+1], suffix_sol[MAX_N+1];
    
void build_sol(int *sol)
{
  stack<char> active_colors;
  for (int i=0; i<N; i++) {
    sol[i+1] = sol[i];
    while (!active_colors.empty() && active_colors.top() > S[i]) active_colors.pop();
    if (active_colors.empty() || active_colors.top() < S[i]) { active_colors.push(S[i]); sol[i+1]++; }
  }
}
     
int main(void)
{
  int Q, i, j;
  cin >> N >> Q >> S;
  build_sol(prefix_sol);
  reverse (S.begin(), S.end());
  build_sol(suffix_sol);  
  for (int q=0; q<Q; q++) {
    cin >> i >> j;
    cout << prefix_sol[i-1] + suffix_sol[N-j] << "\n";
  }
}

For another approach, let $\texttt{prefix}[x]$ denote the answer for the prefix of length $x$. Given $\texttt{prefix}[x]$, how do we compute $\texttt{prefix}[x+1]$?

Let $c$ denote the color of fence segment $x+1$. If $c$ already appeared within the prefix of length $x$ and there is no segment with a lighter color between the last occurrence of $c$ and segment $x+1$, then we can simply extend the stroke that painted that previous occurrence of $c$ to paint segment $x+1$ as well. In this case, $\texttt{prefix}[x+1]=\texttt{prefix}[x]$. Otherwise, the best we can do is to use an additional stroke to paint the new occurrence of $c$, so $\texttt{prefix}[x+1]=\texttt{prefix}[x]+1$.

The code below maintains the lightest color that has appeared since the last occurrence of color $t$ in $\texttt{min_since_last}[t]$. When a new color $c$ is added, we set $\texttt{min_since_last}[t]=\min(\texttt{min_since_last}[t],c)$ for all $t\neq c$ and $\texttt{min_since_last}[c]=c$.

Both of the solutions below run in $\mathcal{O}(N\cdot \Sigma+Q)$ time, where $\Sigma$ is the number of different colors.

Brian Dean's code:

#include <iostream>
using namespace std;
 
#define MAX_N 100000
int N, Q, min_since_last[26], prefix[MAX_N+1], suffix[MAX_N+2];
 
int main(void)
{
  string s;
  cin >> N >> Q >> s;
 
  // Build prefix counts of # of strokes needed
  for (int c=0; c<26; c++) min_since_last[c] = -1;
  for (int i=1; i<=N; i++) {
    int curchar = s[i-1] - 'A'; 
    for (int c=0; c<26; c++) min_since_last[c] = min(curchar, min_since_last[c]);
    prefix[i] = prefix[i-1];
    if (min_since_last[curchar] < curchar) prefix[i]++;
    min_since_last[curchar] = curchar;
  }
 
  // Build suffix counts of # of strokes needed
  for (int c=0; c<26; c++) min_since_last[c] = -1;
  for (int i=N; i>=1; i--) {
    int curchar = s[i-1] - 'A'; 
    for (int c=0; c<26; c++) min_since_last[c] = min(curchar, min_since_last[c]);
    suffix[i] = suffix[i+1];
    if (min_since_last[curchar] < curchar) suffix[i]++;
    min_since_last[curchar] = curchar;
  }
 
  for (int i=0; i<Q; i++) {
    int x, y;
    cin >> x >> y;
    cout << prefix[x-1] + suffix[y+1] << "\n";
  }
}

Danny Mittal's code:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class NoTimeToPaint {
 
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(in.readLine());
        int n = Integer.parseInt(tokenizer.nextToken());
        int m = Integer.parseInt(tokenizer.nextToken());
        String colors = " " + in.readLine();
        int[] last = new int[26];
        int[] prefixes = new int[n + 1];
        for (int j = 1; j <= n; j++) {
            prefixes[j] = prefixes[j - 1];
            int letter = colors.charAt(j) - 'A';
            boolean isLeft = last[letter] == 0;
            for (int lighter = 0; lighter < letter; lighter++) {
                if (last[lighter] > last[letter]) {
                    isLeft = true;
                }
            }
            if (isLeft) {
                prefixes[j]++;
            }
            last[letter] = j;
        }
        Arrays.fill(last, n + 1);
        int[] suffixes = new int[n + 2];
        for (int j = n; j >= 1; j--) {
            suffixes[j] = suffixes[j + 1];
            int letter = colors.charAt(j) - 'A';
            boolean isRight = last[letter] == n + 1;
            for (int lighter = 0; lighter < letter; lighter++) {
                if (last[lighter] < last[letter]) {
                    isRight = true;
                }
            }
            if (isRight) {
                suffixes[j]++;
            }
            last[letter] = j;
        }
        StringBuilder out = new StringBuilder();
        for (int j = 1; j <= m; j++) {
            tokenizer = new StringTokenizer(in.readLine());
            int a = Integer.parseInt(tokenizer.nextToken());
            int b = Integer.parseInt(tokenizer.nextToken());
            out.append(prefixes[a - 1] + suffixes[b + 1]).append('\n');
        }
        System.out.print(out);
    }
}