题目分析

我们需要在字符串中找到最长的连续子串，使得其中字母 J、O、I 的出现次数完全相同。

关键思路

1. 问题转化

   • 设子串从位置 l 到 r，长度为 r-l+1
   • 要求：cnt_J = cnt_O = cnt_I = k
   • 这意味着子串长度必须是 3k

2. 前缀和表示

   • 定义三个前缀和数组：
     • preJ[i]：前 i 个字符中 J 的个数
     • preO[i]：前 i 个字符中 O 的个数
     • preI[i]：前 i 个字符中 I 的个数
   • 对于子串 [l, r]，各字母出现次数为：
     • J_count = preJ[r] - preJ[l-1]
     • O_count = preO[r] - preO[l-1]
     • I_count = preI[r] - preI[l-1]

3. 等量关系转化

   • 要求 J_count = O_count = I_count
   • 这等价于：
     • preJ[r] - preJ[l-1] = preO[r] - preO[l-1]
     • preJ[r] - preJ[l-1] = preI[r] - preI[l-1]
   • 整理得：
     • preJ[r] - preO[r] = preJ[l-1] - preO[l-1]
     • preJ[r] - preI[r] = preJ[l-1] - preI[l-1]

4. 核心观察

   • 定义差值状态：(preJ[i] - preO[i], preJ[i] - preI[i])
   • 如果两个位置 l-1 和 r 的差值状态相同，那么子串 [l, r] 就是满足条件的
   • 我们只需要找到相同差值状态出现的最远距离

5. 算法步骤

   • 初始化哈希表，记录每个差值状态第一次出现的位置
   • 遍历字符串，计算当前的前缀和和差值状态
   • 如果当前差值状态之前出现过，计算距离并更新答案
   • 如果当前差值状态是新的，记录其第一次出现的位置
   • 特别处理初始状态 (0, 0)，对应空前缀

6. 复杂度分析

   • 时间复杂度：O(N)，只需一次遍历
   • 空间复杂度：O(N)，用于存储哈希表

这种方法巧妙地利用了前缀和的差分性质，将原本需要 O(N²) 的暴力枚举优化到了线性时间复杂度。