题解

题目描述

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

思路

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

代码分析

1. 前缀和数组构建：遍历字符串，计算每个位置的状态。
2. 线性最长子串计算：利用哈希表记录状态的最早出现位置，寻找最大间隔。
3. 环形最长子串计算：利用哈希表记录状态的最大出现位置，结合异或运算寻找有效子串。
4. 总状态判断：检查总状态是否为有效状态，决定是否将整个字符串长度作为候选解。

问题本质

通过状态压缩和前缀和，将问题转化为寻找相同状态的间隔，结合环形处理技巧，高效求解最长子串长度。

cpp

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    string s;
    cin >> s; // 输入字符串
    int n = s.size(); // 字符串长度
    vector<int> pre(n + 1, 0); // 前缀和数组，记录每个位置的状态

    // 计算前缀和数组
    for (int i = 0; i < n; ++i) {
        char c = s[i];
        int mask = 0; // 状态掩码
        if (c == 'l') mask = 1 << 0; // 'l'对应第0位
        else if (c == 'o') mask = 1 << 1; // 'o'对应第1位
        else if (c == 'x') mask = 1 << 2; // 'x'对应第2位
        pre[i + 1] = pre[i] ^ mask; // 更新前缀和状态
    }
    int S = pre[n]; // 整个字符串的总状态

    // 线性情况：寻找最长子串
    unordered_map<int, int> earliest; // 记录每个状态的最早出现位置
    earliest[0] = 0; // 初始状态为0
    int max_linear = 0; // 线性情况下的最大长度
    for (int i = 1; i <= n; ++i) {
        int current = pre[i]; // 当前状态
        if (earliest.count(current)) { // 如果当前状态之前出现过
            max_linear = max(max_linear, i - earliest[current]); // 更新最大长度
        } else {
            earliest[current] = i; // 记录当前状态的最早位置
        }
    }

    // 环形情况：寻找最长子串
    unordered_map<int, int> latest; // 记录每个状态的最大出现位置
    latest[pre[0]] = 0; // 初始状态为0
    int max_circular = 0; // 环形情况下的最大长度
    for (int j = 1; j <= n; ++j) {
        int current = pre[j]; // 当前状态
        int target = current ^ S; // 目标状态
        if (latest.count(target)) { // 如果目标状态之前出现过
            int i = latest[target]; // 目标状态的最大位置
            int length = i + n - j; // 计算环形子串长度
            max_circular = max(max_circular, length); // 更新最大长度
        }
        if (!latest.count(current) || j > latest[current]) { // 更新当前状态的最大位置
            latest[current] = j;
        }
    }

    // 判断整个字符串是否满足条件
    bool is_total_even = ((S & (1 << 0)) == 0) && ((S & (1 << 1)) == 0) && ((S & (1 << 2)) == 0);
    int ans = max(max_linear, max_circular); // 取线性和环形情况的最大值
    if (is_total_even) { // 如果整个字符串满足条件
        ans = max(ans, n); // 更新结果为整个字符串长度
    }
    cout << ans << endl; // 输出结果
    return 0;
}

python

s = input().strip()  # 输入字符串
n = len(s)  # 字符串长度
pre = [0] * (n + 1)  # 前缀和数组，记录每个位置的状态

# 计算前缀和数组
for i in range(n):
    c = s[i]
    mask = 0  # 状态掩码
    if c == 'l':
        mask = 1 << 0  # 'l'对应第0位
    elif c == 'o':
        mask = 1 << 1  # 'o'对应第1位
    elif c == 'x':
        mask = 1 << 2  # 'x'对应第2位
    pre[i + 1] = pre[i] ^ mask  # 更新前缀和状态
S = pre[n]  # 整个字符串的总状态

# 线性情况：寻找最长子串
earliest = {0: 0}  # 记录每个状态的最早出现位置
max_linear = 0  # 线性情况下的最大长度
for i in range(1, n + 1):
    current = pre[i]  # 当前状态
    if current in earliest:  # 如果当前状态之前出现过
        max_linear = max(max_linear, i - earliest[current])  # 更新最大长度
    else:
        earliest[current] = i  # 记录当前状态的最早位置

# 环形情况：寻找最长子串
latest = {pre[0]: 0}  # 记录每个状态的最大出现位置
max_circular = 0  # 环形情况下的最大长度
for j in range(1, n + 1):
    current = pre[j]  # 当前状态
    target = current ^ S  # 目标状态
    if target in latest:  # 如果目标状态之前出现过
        i_val = latest[target]  # 目标状态的最大位置
        length = i_val + n - j  # 计算环形子串长度
        max_circular = max(max_circular, length)  # 更新最大长度
    if current not in latest or j > latest.get(current, -1):  # 更新当前状态的最大位置
        latest[current] = j

# 判断整个字符串是否满足条件
is_total_even = (S & (1 << 0)) == 0 and (S & (1 << 1)) == 0 and (S & (1 << 2)) == 0
ans = max(max_linear, max_circular)  # 取线性和环形情况的最大值
if is_total_even:  # 如果整个字符串满足条件
    ans = max(ans, n)  # 更新结果为整个字符串长度
print(ans)  # 输出结果

java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next(); // 输入字符串
        int n = s.length(); // 字符串长度
        int[] pre = new int[n + 1]; // 前缀和数组，记录每个位置的状态
        pre[0] = 0; // 初始状态为0

        // 计算前缀和数组
        for (int i = 0; i < n; ++i) {
            char c = s.charAt(i);
            int mask = 0; // 状态掩码
            if (c == 'l') mask = 1 << 0; // 'l'对应第0位
            else if (c == 'o') mask = 1 << 1; // 'o'对应第1位
            else if (c == 'x') mask = 1 << 2; // 'x'对应第2位
            pre[i + 1] = pre[i] ^ mask; // 更新前缀和状态
        }
        int S = pre[n]; // 整个字符串的总状态

        // 线性情况：寻找最长子串
        Map<Integer, Integer> earliest = new HashMap<>(); // 记录每个状态的最早出现位置
        earliest.put(0, 0); // 初始状态为0
        int maxLinear = 0; // 线性情况下的最大长度
        for (int i = 1; i <= n; ++i) {
            int current = pre[i]; // 当前状态
            if (earliest.containsKey(current)) { // 如果当前状态之前出现过
                maxLinear = Math.max(maxLinear, i - earliest.get(current)); // 更新最大长度
            } else {
                earliest.put(current, i); // 记录当前状态的最早位置
            }
        }

        // 环形情况：寻找最长子串
        Map<Integer, Integer> latest = new HashMap<>(); // 记录每个状态的最大出现位置
        latest.put(pre[0], 0); // 初始状态为0
        int maxCircular = 0; // 环形情况下的最大长度
        for (int j = 1; j <= n; ++j) {
            int current = pre[j]; // 当前状态
            int target = current ^ S; // 目标状态
            if (latest.containsKey(target)) { // 如果目标状态之前出现过
                int iVal = latest.get(target); // 目标状态的最大位置
                int length = iVal + n - j; // 计算环形子串长度
                maxCircular = Math.max(maxCircular, length); // 更新最大长度
            }
            if (!latest.containsKey(current) || j > latest.get(current)) { // 更新当前状态的最大位置
                latest.put(current, j);
            }
        }

        // 判断整个字符串是否满足条件
        boolean isTotalEven = ((S & (1 << 0)) == 0) && ((S & (1 << 1)) == 0) && ((S & (1 << 2)) == 0);
        int ans = Math.max(maxLinear, maxCircular); // 取线性和环形情况的最大值
        if (isTotalEven) { // 如果整个字符串满足条件
            ans = Math.max(ans, n); // 更新结果为整个字符串长度
        }
        System.out.println(ans); // 输出结果
    }
}

题目内容

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

输入描述

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

输出描述

输出是一个整数

备注

• $1 ≤ s.length ≤ 5 * 10^5$

• $s$ 只包含小写英文字母

样例1

输入

alolobo

输出

6

说明

最长子字符串之一是 "$alolob$"，它包含 '$l$'，'$o$' 各$2$个，以及 $0$ 个 '$x$'。

样例2

输入

looxdolx

输出

7

说明

最长的子字符串是"$oxdolxl$"，由于是首尾连接在一起的，所以最后一个 '$x$' 和开头的 '$l$' 是连接在一起的，此字符串包含 $2$ 个 '$l$'，$2$个'$o$'，$2$个'$x$'

样例3

输入

bcbcbc

输出

6

说明

这个示例中，字符串 "$bcbcbc$" 本身就是最长的，因为 '$l$'、'$o$'、'$x$' 都出现了 $0$ 次。