P4206. 环中最长字串2

解题思路

考虑非环字符串

首先考虑比较简单的情况，假设字符串并不是一个环型字符串，而是一个普通的字符串。

通过前缀确定任意连续子串的情况

假设我们事先已知任意一个从 0 开始的子串包含字母的情况，那么子串 s[i:j] 中包含 "l"、"o"、"x" 字符的个数，为子串 s[:j] 中 "l"、"o"、"x" 字符的个数分别减去子串 s[:i] 中的 "l"、"o"、"x" 字符的个数。

譬如，假设 s = "llolobo"，如果已知：

• s[:1] 中包含 1 个 "l"、0 个 "o"、0 个 "x"
• s[:4] 中包含 3 个 "l"、1 个 "o"、0 个 "x"

那么容易计算得到 s[1:4] 中包含：

• 3 - 1 = 2 个 "l"
• 1 - 0 = 1 个 "o"
• 0 - 0 = 0 个 "x"

只考奇偶性而非具体数量

根据加减法的奇偶性，我们知道：

• 奇数 - 奇数 = 偶数
• 偶数 - 偶数 = 偶数
• 奇数 - 偶数 = 奇数
• 偶数 - 奇数 = 奇数

由于题目只要求考虑 "l"、"o"、"x" 字符都恰好出现了偶数次（而非某些特定值）子字符串。我们可以进一步简化问题，不考虑每一个字符串前缀包含的 "l"、"o"、"x" 字符的个数，而是只考虑个数的奇偶性。

譬如，假设 s = "llolobo"，如果已知：

• s[:1] 中包含奇数个 "l"、偶数个 "o"、偶数个 "x"
• s[:4] 中包含偶数个 "l"、奇数个 "o"、偶数个 "x"

那么容易计算得到 s[1:4] 中包含：

• 奇数 - 奇数 = 偶数个 "l"
• 奇数 - 偶数 = 奇数个 "o"
• 偶数 - 偶数 = 偶数个 "x"

三个差值均为偶数的情况

题目要求考虑 "l"、"o"、"x" 字符都恰好出现了偶数次的子字符串。如果某个子字符串 s[i:j] 包含的三种字符均出现了偶数次，则意味着两个对应的前缀 s[:i] 和 s[:j] 所包含的三种字符的奇偶性必须相等。

将奇偶性状态压缩为数字

一共有 3 个考虑的字符，每个前缀有奇或偶 2 种状态。故前缀的奇偶性一共有 2^3 = 8 种可能性。

假设我们用 1 表示奇，0 表示偶。这里的 8 种可能性当然可以用一个长度为 3 的哈希表或列表来表示，比如：

但是这样并不方便我们进行做差的操作。

我们可以考虑把 2^3 = 8 种可能性使用二进制映射到 0-7 这 8 个数字上。

对十进制数进行做差，就非常方便了。这种技巧就叫做状态压缩（State compression）。

状态压缩后的前缀和数组的构建

因此，我们的前缀和数组就可以只用数字来表示了。其构建过程如下：

• 初始化 pre_sum = [0]，表示最开始的前缀为空串，包含的三种字符均为偶数。
• 遍历原字符串 s 中的字符 ch，若：
• ch == "l"，前缀中包含 "l" 的个数的奇偶性发生改变。新的前缀和应该和其上一个前缀和 pre_sum[-1] 中的 "l" 的奇偶性相反。由于 "l" 是二进制数的第三位（从低位数起），故新的前缀和为 pre_sum[-1] ^ 4。
• ch == "o"，前缀中包含 "o" 的个数的奇偶性发生改变。新的前缀和应该和其上一个前缀和 pre_sum[-1] 中的 "o" 的奇偶性相反。由于 "o" 是二进制数的第二位（从低位数起），故新的前缀和为 pre_sum[-1] ^ 2。
• ch == "x"，前缀中包含 "x" 的个数的奇偶性发生改变。新的前缀和应该和其上一个前缀和 pre_sum[-1] 中的 "x" 的奇偶性相反。由于 "x" 是二进制数的第一位（从低位数起），故新的前缀和为 pre_sum[-1] ^ 1。
• ch 不是这三种字符串，则新的前缀和和上一个前缀和 pre_sum[-1] 一致。为了保持算法的统一性，可以写作 pre_sum[-1] ^ 0。

具体代码为：

或者构建一个关于字母和数字映射的哈希表，进一步简写：

根据前缀和数组找到最长子字符串

在构建完前缀和数组之后，问题进一步退化为：找到前缀和数组中两个相等的数的最远距离。

这个问题和【哈希表】2023Q1A-相同数字的积木游戏几乎完全一致。

我们可以遍历整个前缀和数组，使用一个哈希表 dic 来储存每一个数字 num 第一次出现时的下标。在后续再次找到这个数字 num 时，已知当前下标为 i，那么这两个相同数字的最远距离为 i - dic[num]，将其和全局的答案变量 ans 比较并更新 ans。这也是哈希表在储存下标类型问题中的应用。

因此，如果仅仅考虑非环字符串，整体的代码为：

这当然是不对的，通过率约为 50%。别忘了我们还没考虑环的情况。

考虑环形字符串

原字符串自身拼接

关于环的处理，一个非常常见的操作是遍历原数组/字符串两次，或者遍历原数组/字符串自身拼接后的结果。因此，我们在构建前缀和的时候，应该要考虑的是原字符串 s 自身拼接后的结果 s + s。

譬如原字符串是 s = "ooxk"，实际上我们要考虑字符串自身拼接后的结果 ss = "ooxkooxk"，对这个拼接后的字符串考虑前缀和才是正确的。其对应的前缀和数组为 [0, 2, 0, 1, 1, 3, 1, 0, 0]。正确的答案应该是我们要下标差为 3 的两个相等的 1，表示子串 "koo"。

储存下标哈希表的修正

既然考虑了环型字符串，并且对前缀和数组进行了修正，那么相应的储存下标的哈希表也要进行修正。我们显然不能按照原来只储存第一次出现 num 的下标的方式来构建哈希表了。

设原字符串的长度 n = len(s)。当某个数字 num 最新出现的下标 i 和之前数字 num 最早出现过的下标 j 之间的差值 i - j > n 的时候，说明子串 ss[i:j] 已经超过了 1 圈，不是原字符串 s 中真正的子串。此时我们不能再使用 j 作为最早出现过的下标了，而应该进一步考虑 j 的下一个值与 i 的距离。

问题也对应地进行修正：找到前缀和数组中，不超过原字符串长度 `len(s)` 的两个相等的数的最远距离。因此，在遍历过程中，我们必须储存值为 num 的所有下标。

但又由于在使用这些下标的过程中，我们总是优先使用最早出现的下标，因此下标的储存符合先进先出的特点。很容易想到，应该使用队列来储存同一个数字 num 所出现过的下标。

因此我们可以这样修正哈希表：

• key 保持不变，仍然为数字 num
• value 从单纯储存第一次出现的下标，修改为一个储存了值为 num 的所有下标的队列。

那么遍历前缀和数组的过程相应地进行修改，遍历下标 i 和数字 num：

• 将当前下标 i 储存在哈希表 dic 中对应的队列 dic[num] 里
• 使用 while 循环，持续判断该队列的队头元素 dic[num][0] 是否和当前下标 i 的差值大于 len(s)
• 若是，则说明超过了环的一圈，将队头元素弹出
• 弹出后，队头的新元素 dic[num][0] 则会是和当前下标 i 距离最远的值为 num 的下标
• 当前下标 i 和距离最远的值为 num 的下标 dic[num][0] 之间的距离为 i - dic[num][0]，将其和 ans 比较并进行答案更新。

这样我们就利用队列先进先出的特点，完成了哈希表和遍历过程的修正。整体代码为：

复杂度分析

设 n 为原字符串 s 的长度。

• 时间复杂度：O(n)。第一段循环遍历拼接串 s+s（长度 2n），每个字符只做一次异或就得到新的前缀状态，构建出的 pre_sum 数组共 2n+1 项，为 O(n)。第二段循环遍历 pre_sum 的每个下标：每个下标恰好入队一次；while 循环弹出队头时，每个下标至多被弹出一次，因此全过程所有弹出操作合计不超过 2n+1 次，摊还下来每轮是 O(1)，整段仍为 O(n)。两段相加即 O(n)。
• 空间复杂度：O(n)。pre_sum 数组占 2n+1 个整数；哈希表 dic 的 key 只有 8 种可能的压缩状态（三个字符各自奇偶性的组合），但各状态队列合计最多存放 2n+1 个下标，故整体为 O(n)。

瓶颈在两趟线性扫描本身。状态压缩把「比较三个字符出现次数的奇偶性」变成单个整数的相等判断，配合队列按「距离不超过一圈」及时弹出过期下标，是整体保持线性的关键。