This problem is a query problem, so we need to consider what data to maintain and how to process queries to respond to queries fast.

First, let us consider how to answer queries. Let \(n\) be the answer to some \((L, R)\). Then,

• any \(11/22\) string of length at most \(n\) is contained in the substring from \(L\)-th through \(R\)-th characters of \(S\) as a subsequence, but
• no \(11/22\) substring of length greater than \(n\) is contained as a subsequence.

Using this monotonicity, we can come up with the following binary search approach:

• Initially, let \(l=-1, r=N+1\).
• While \(r - l \geq 1\), do the following.
  • Let \(m = \lfloor (l+r) / 2 \rfloor\).
  • Check if an \(11/22\) string of length \(2m+1\) exists as a subsequence within the segment.
  • If it exists, let \(l = m\); otherwise, let \(r = m\).
• If the final \(l\) is \(-1\), there is no \(11/22\) string as a subsequence of the current segment. Otherwise, there exists an \(11/22\) string of length \((2l+1)\) as a subsequence, which is the longest possible.

While this algorithm does work fine, we have not figured out how to solve the following subproblem:

• Check if an \(11/22\) string of length \(2m+1\) exists as a subsequence within the segment.

Once we solve it, the original problem can be solved in a total of \(\mathrm{O}(Q \log N \times (\text{complexity of subproblem}))\), so we consider how to solve the subproblem.

This subproblem can be solved by doing an appropriate precalculation and referring to it appropriately. Specifically, precalculate the following sequences:

• \(v_1\): the monotonically increasing sequence consisting of indices \(i\) with \(S[i] =\) 1
• \(v_2\): the monotonically increasing sequence consisting of indices \(i\) with \(S[i] =\) 2
• \(v_3\): the monotonically increasing sequence consisting of indices \(i\) with \(S[i] =\) /

Then the subproblem can be solved with an appropriate binary search in a total of \(\mathrm{O}(\log N)\) time. (For more details, refer to the sample code.) One can even improve it to \(\mathrm{O}(1)\) by maintaining information differently.

Therefore, the problem has been solved in a total of \(\mathrm{O}(N + Q \log^2 N)\) or \(\mathrm{O}(N + Q \log N)\) time, which is fast enough.

• Sample code (C++, \(\mathrm{O}(N + Q \log^2 N)\))

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int lb(const vector<int>& v, int x) {
  return lower_bound(begin(v), end(v), x) - begin(v);
}
int sz(const vector<int>& v) { return v.size(); }

int main() {
  int N, Q;
  string S;
  cin >> N >> Q >> S;

  vector<int> idx1, idx2, idxs;
  for (int i = 0; i < N; i++) {
    (S[i] == '1' ? idx1 : S[i] == '2' ? idx2 : idxs).push_back(i);
  }
  while (Q--) {
    int l, r;
    cin >> l >> r;
    --l;
    
    // Is there a 11/22 string containing `len` 1's and 2's?
    auto f = [&](int len) -> bool {
      if (len == 0) {
        // Find `/`
        int j = lb(idxs, l);
        if (j >= sz(idxs)) return false;
        return idxs[j] < r;
      }
      // Find `1`
      int i = lb(idx1, l);
      if (i + len - 1 >= sz(idx1)) return false;
      // Find `/`
      int j = lb(idxs, idx1[i + len - 1]);
      if (j >= sz(idxs)) return false;
      // Find `2`
      int k = lb(idx2, idxs[j]);
      if (k + len - 1 >= sz(idx2)) return false;
      return idx2[k + len - 1] < r;
    };

    int ok = -1, ng = N + 1;
    while (ok + 1 < ng) {
      int m = (ok + ng) / 2;
      (f(m) ? ok : ng) = m;
    }
    cout << (ok == -1 ? 0 : ok * 2 + 1) << "\n";
  }
}