题目内容

小红有一个长度为n 的字符串$S_1S_2···Sn$，字符串中只包含小写字母，每个字母代表一种颜色。

小红有$q$次询问，每次询问如果将区间$[l,r]$染成相同的颜色，至少需要修改多少个字母，才能使得区间$[l,r]$染成相同的颜色。请你帮助小红解决这个问题。

解题思路

问题分析

给定长度为 $n$ 的字符串 $S$，包含小写字母。每个查询给出区间 $[l, r]$，要求将区间内的所有字符都变成同一个字母，最少需要修改多少个字符？

本质上就是在区间 $[l, r]$ 中，选一个出现次数最多的字母，将其他字符都改为该字母。若该字母出现次数为 $\text{maxCnt}$，区间长度为 $\text{len}=r-l+1$，则最少修改次数为 $\text{ans} = \text{len}$ - $\text{maxCnt}.$

数据结构与预处理

• 构造一个前缀和数组 cnt[i][c]，表示 $S[1..i]$ 中字母 c 的出现次数。