图中先把相同字符的位置减去顺序号，聚成连续段的代价转成到中位数的距离和。
字符串里几个相同字母隔着其他字符，最多交换 m 次相邻字符，能把多长的一段相同字母聚在一起？直接搜索所有交换会迅速膨胀。更好的入口是先忘掉其他字符的身份，只记录目标字符出现在哪里。
从位置列表开始
用自设字符串 AbcAdA，三个 A 的下标依次是零、三、五。若希望把这三个 A 聚成连续段，不需要规定每个其他字符最后是哪一个位置，只要计算 A 跨过多少个其他字符即可。
相同字符可以按原来的先后顺序对应到目标位置，不必互相穿越。想选出 k 个聚拢时，可以考察该字符出现列表中的连续 k 个；若跳过中间同类字符，它也会影响最终连续段，不能把它当成一个必须跨越的异类障碍。
对每种字符分别收集位置，问题就转成在一个有序整数列表上寻找合适窗口。字符是否按大小写区分、下标按什么单位计数，应由输入口径先确定，不要实现到一半才改变“一个字符”的含义。
连续目标位置带来一个巧变形
设选中位置为 p0、p1、p2，最终希望放在 t、t+1、t+2。总移动代价是三个绝对距离之和。把每一项的顺序偏移移过去，就相当于计算 p0、p1-1、p2-2 到同一个位置 t 的距离和。
因此定义 q_i=p_i-i。原位置至少递增一，所以 q 列表非递减。把原本“放成连续位置”的目标，改成“调整后的位置聚到同一个点”，就可以使用绝对距离和在中位数处取得最小值的性质。
若窗口不是从该字符的第零次出现开始，统一使用全局出现序号也可以，目标 t 会相应平移，最小代价不受这个共同偏移影响。关键是同一个窗口内采用一致的序号约定。
一个例子看出中位数的作用
三个 A 的位置为 [0，3，5]，调整后得到 [0，2，3]。中位数是二，到它的距离和为二加零加一，最少需要三次相邻交换。最终可以让三个 A 位于二、三、四，把字符串变成 bcAAAd。
如果预算只有两次，三个 A 聚拢超支，但后两个 A 之间只隔一个 d，一次交换就能形成 AA。因此该输入预算二时的最长长度为二，预算三时可以达到三。这里的数值是自设算例，不来自真实文本性能测试。
偶数个位置有两个中间点，取其中一个中位数即可，最小距离和相同。无需枚举所有可能的连续段起点，也不应该把“取平均数”替代中位数：平均数优化的是另一种平方距离目标。
前缀和让窗口代价快速求出
对 q 建前缀和。窗口中位点左侧的代价，是“左侧数量乘中位值”减去左侧元素之和；右侧则是“右侧元素之和”减去“右侧数量乘中位值”。各项都能由前缀和在常数次运算内得到。
给定段长 k，扫描该字符的所有连续出现窗口，只要某个最小代价不超过预算，这个 k 就可行。更短段也可从可行段中取出，因此可行性具有用于二分长度的单调性。
把所有字符的窗口检查加起来，可以设计总计 O(n log n) 的方案，位置收集和前缀和占 O(n) 空间。这里按常规整数运算成本分析，实际还需让索引和距离累加使用足够的数值范围。
用独立交换搜索核对公式
小字符串可以真的枚举相邻交换，并比较每个预算下的最长连续段，与位置算法结果对照。这个参考算法很慢，却独立于中位数推导，适合抓住窗口偏移、空串和预算边界错误。
还应覆盖全相同字符、预算零、只出现一次的字符，以及预算足够大能全部聚拢的情况。不能只测一个三字符例子，就认为二分条件和前缀和下标一定正确。
这道题的关键是先消除连续目标自带的顺序偏移。如果直接对原位置 [0，3，5] 求到中位数三的距离和，为什么会把本来相邻的目标 A 之间也错误地计算成需要消除的距离？