题目内容

给你一个字符串 $s$，字符串 $s$ 首尾相连成一个环形，请你在环中找出 '$l$'、'$o$'、'$x$' 字符都恰好出现了偶数次最长子字符串的长度。

输入描述

输入是一串小写的字母组成的字符串

题解

题目描述

给定一个环形字符串，找出其中满足字符 'l'、'o'、'x' 出现次数均为偶数的最长子字符串的长度。

思路

1. 前缀和与状态压缩：使用前缀和数组记录每个位置的状态，状态由三位二进制数表示，分别对应 'l'、'o'、'x' 出现次数的奇偶性。
2. 线性情况处理：遍历字符串，维护哈希表记录每个状态的最早出现位置，计算最长有效子串长度。
3. 环形情况处理：考虑环形子串的情况，维护哈希表记录每个状态的最大出现位置，计算可能的环形子串长度。
4. 总状态判断：若整个字符串的总状态满足条件（三个字符出现次数均为偶数），则整个字符串长度也是一个候选解。