最长子字符串的长度(二) - 华为OD统一考试

OD统一考试（C卷）

分值： 200分

题解： Java / Python / C++

alt

题目描述

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

输入描述

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

输出描述

输出是一个整数。

补充说明：

1 <= s.length <= 5 x 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"。

题解

使用一个整数 status 代表状态（状态压缩）：

第 0 位为 1 表示 l 出现奇数次；
第 1 位为 1 表示 o 出现奇数次；
第 2 位为 1 表示 x 出现奇数次；

这样当 l, o, x 都为偶数时 status = 0。

然后双层循环寻找符合条件的最大子字符串长度。

时间复杂度： O(n^2)

Java

import java.util.Scanner;
/**
 * @author code5bug
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String in = scanner.next();

        int len = in.length();
        int max_len = 0;
        for (int i = 0; i < len; i++) {
            for (int j = i, status = 0; j < i + len; j++) {
                char c = in.charAt(j % len);

                if (in.charAt(i) == 'l') {
                    status ^= 1;
                } else if (in.charAt(i) == 'o') {
                    status ^= 2;
                } else if (in.charAt(i) == 'x') {
                    status ^= 4;
                }

                // 'l'、'o'、'x' 字符都恰好出现了偶数次
                if (status == 0) {
                    max_len = Math.max(max_len, (j - i + 1));
                }
            }
        }

        System.out.println(max_len);
    }
}

Python

in_str = input()

len_str = len(in_str)
max_len = 0

for i in range(len_str):
    for j in range(i, i + len_str):
        c = in_str[j % len_str]

        status = 0
        if in_str[i] == 'l':
            status ^= 1
        elif in_str[i] == 'o':
            status ^= 2
        elif in_str[i] == 'x':
            status ^= 4

        # 'l'、'o'、'x' 字符都恰好出现了偶数次
        if status == 0:
            max_len = max(max_len, (j - i + 1))

print(max_len)

C++

#include <iostream>
#include <string>
using namespace std;

int main() {
    string in;
    cin >> in;

    size_t len = in.length();
    int max_len = 0;
    for (int i = 0; i < len; i++) {
        for(int j = i, status = 0; j < i + len; j++) {
            char c = in[j % len];

            if(in[i] == 'l') status ^= 1;
            else if(in[i] == 'o') status ^= 2;
            else if(in[i] == 'x') status ^= 4;

            // 'l'、'o'、'x' 字符都恰好出现了偶数次
            if(status == 0) { 
                max_len = max(max_len, (j - i + 1));
            }
        }
    }

    cout << max_len << endl;

    return 0;
}