题目大意

给定一个长度为 $N$ 的字符串 $S$，每个字符代表一种颜色（26个小写字母）。对于任意连续子串，定义其多彩值为：

$$\text{多彩值} = \frac{\text{子串中不同颜色的数量}}{\text{子串长度}} $$

要求找到一个连续子串，使得其多彩值最小。

问题分析

关键观察

1. 比值性质：多彩值是不同颜色数与长度的比值，目标是最小化这个比值
2. 取值范围：多彩值 $\in [\frac{1}{n}, 1]$，其中 $n$ 是子串长度
3. 颜色限制：只有26种可能颜色，这是一个重要的约束条件

数学洞察

设 $f(l, r)$ 表示子串 $S[l:r]$ 中不同颜色的数量，则我们需要最小化：

$$\min\limits_{1 \leq l \leq r \leq N} \frac{f(l, r)}{r-l+1} $$

算法设计

方法一：基于固定颜色数的滑动窗口

核心思想： 由于颜色种类最多只有26种，我们可以枚举子串中可能包含的颜色种类数 $k$（从1到26），对于每个 $k$，找到包含恰好 $k$ 种颜色的最长连续子串。

具体步骤：

1. 对于 $k = 1$ 到 $26$：

   • 使用双指针维护一个滑动窗口 $[l, r]$
   • 保持窗口内颜色种类数 $\leq k$
   • 当窗口内颜色种类数恰好为 $k$ 时，计算比值 $\frac{k}{\text{窗口长度}}$
   • 记录当前 $k$ 下的最小比值对应的子串

2. 在所有 $k$ 对应的候选解中，选择比值最小的作为最终答案

正确性证明：

• 最优解一定对应某个固定的颜色种类数 $k$
• 对于固定的 $k$，最长的子串会给出最小的比值 $\frac{k}{\text{长度}}$
• 枚举所有可能的 $k$ 可以覆盖所有可能的最优解

复杂度分析：

• 时间复杂度：$O(26 \times N) = O(N)$
• 空间复杂度：$O(1)$（只需要常数大小的计数数组）

方法二：比值二分搜索

核心思想： 二分搜索可能的多彩值 $x$，验证是否存在子串满足 $\frac{f(l, r)}{r-l+1} \leq x$。

具体步骤：

1. 二分搜索多彩值 $x \in [0, 1]$
2. 对于每个 $x$，验证是否存在子串满足条件：
   • 将问题转化为：是否存在子串使得 $f(l, r) \leq x \times (r-l+1)$
   • 这等价于 $x \times (r-l+1) - f(l, r) \geq 0$
3. 使用滑动窗口验证可行性

复杂度分析：

• 时间复杂度：$O(N \log \epsilon^{-1})$，其中 $\epsilon$ 是精度要求
• 空间复杂度：$O(1)$

实现细节

滑动窗口的实现技巧

// 伪代码
int count[26]; // 颜色计数数组
int l = 0, color_types = 0;
for (int r = 0; r < n; r++) {
    // 添加右端点
    if (count[S[r]-'a'] == 0) color_types++;
    count[S[r]-'a']++;
    
    // 收缩左端点直到颜色种类数 <= k
    while (color_types > k) {
        count[S[l]-'a']--;
        if (count[S[l]-'a'] == 0) color_types--;
        l++;
    }
    
    // 更新答案
    if (color_types == k) {
        double ratio = (double)k / (r - l + 1);
        // 记录最优解
    }
}

优化技巧

1. 提前终止：当当前最优比值已经很小且 $k$ 增大时，可以提前终止
2. 边界处理：注意空串和单字符的特殊情况
3. 浮点数比较：由于是比值比较，注意浮点精度问题，可以转化为整数比较避免精度误差

特殊情况考虑

1. 全相同字符：此时最优解是整个字符串，比值为 $\frac{1}{N}$
2. 所有字符不同：此时最优解是任意长度为1的子串，比值为1
3. 多个最优解：题目允许输出任意一个最优解

算法选择建议

• 推荐方法一：基于固定颜色数的滑动窗口

  • 思路直观，易于实现
  • 时间复杂度优秀 $O(26N)$
  • 不需要处理浮点数精度问题
  • 充分利用了颜色种类有限的特性

• 方法二：比值二分搜索

  • 更通用，适用于颜色种类较多的情况
  • 但实现相对复杂，需要处理浮点数比较

总结

本题的关键在于利用颜色种类有限（26种）这一重要约束，将问题转化为枚举颜色种类数并使用滑动窗口寻找最优解。这种方法既保证了正确性，又具有优秀的时间复杂度，是解决此类比值最小化问题的经典思路。

核心技巧：将最小化比值问题转化为枚举分子（颜色种类数），然后对于每个固定的分子，最大化分母（子串长度）来获得最小比值。