クエリ 2 である文字列 \(c\) が何回出現したかを高速に数える方法を考えます。もしこれが高速で数えられることができれば \(c=\) a, b, \(\ldots\), z に対して数え、その最大値を出力することでクエリ 2 に答えることができます。

ここで、ある文字列 \(c\) を固定すると、文字列の各文字は \(c\) か \(c \) 以外かに分類されます。すると、各クエリは \(c\) を \(1\) に、 \(c\) 以外を \(0\) に対応させた整数列に対する変更クエリ・総和を求めるクエリに対応します。これは Fenwick Tree や Segment Tree でそれぞれ \(O(\log N)\) 時間で行うことができます。

以上を適切に実装することでこの問題に正答することができます。計算量は文字種を \(\sigma\) として \(O(\sigma(N+Q\log N))\) です。

実装例(Python3)

from atcoder import fenwicktree
import sys
input = sys.stdin.readline

n, q = map(int, input().split())
s = input()
ss = [ord(s[i]) - ord("a") for i in range(n)]
f = [fenwicktree.FenwickTree(n) for _ in range(26)]
for i in range(n):
    f[ss[i]].add(i, 1)
for _ in range(q):
    a = list(map(str, input().split()))
    if a[0] == "1":
        p = int(a[1]) - 1
        c = ord(a[2]) - ord("a")
        f[ss[p]].add(p, -1)
        ss[p] = c
        f[ss[p]].add(p, 1)
    else:
        l, r = int(a[1]) - 1, int(a[2])
        ans = 0
        for i in range(26):
            ans = max(ans, f[i].sum(l, r))
        print(ans)