最新华为OD机试真题-环形字符串最长子串(200分)

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

💻 ACM金牌🏅️团队 ｜ 编程一对一辅导

✨ 本系列打算持续跟新华为OD-D卷的三语言AC题解

👏 感谢大家的订阅➕ 和 喜欢💗 和手里的小花花🌸

最新华为OD机试D卷目录，全、新、准，题目覆盖率达 95% 以上，支持题目在线评测

最新华为OD机试目录: https://www.nowcoder.com/discuss/636153620743897088?sourceSSR=users

📎 在线评测链接

环形字符串最长子串(200分)

🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁～

🍓OJ题目截图

🫥 环形字符串最长子串

问题描述

LYA 最近在研究一种特殊的字符串问题。给定一个由小写字母组成的字符串 ,将该字符串首尾相连形成一个环形字符串。LYA 的任务是在这个环形字符串中找出一个最长的子串,使得子串中字符 'I'、'o' 和 'x' 都出现偶数次(包括 0 次)。

例如,对于字符串 "alolobo",最长的满足条件的子串是整个字符串本身,长度为 7。而对于字符串 "looxdolx",最长的满足条件的子串是 "oxdolxl",长度为 7。

输入格式

输入是一个字符串 ,由小写字母组成,长度在 范围内。

输出格式

输出一个整数,表示满足条件的最长子串的长度。

样例输入 1

alolobo

样例输出 1

6

样例解释 1

最长的满足条件的子串是 "alolobo" 本身,长度为 6。它包含 2 个 'I'、2 个 'o' 和 0 个 'x'。

样例输入 2

looxdolx

样例输出 2

7

样例解释 2

最长的满足条件的子串是 "oxdolxl",长度为 7。由于字符串是环形的,所以最后一个 'x' 和开头的 'l' 是相连的。该子串包含 2 个 'I'、2 个 'o' 和 2 个 'x'。

样例输入 3

bcbcbc

样例输出 3

6

样例解释 3

这个示例中,字符串 "bcbcbc" 本身就是最长的满足条件的子串,因为它不包含 'I'、'o' 和 'x'。

数据范围

• ,其中 表示字符串 的长度。
• 只包含小写字母。

题解

这个问题可以使用滑动窗口的思想来解决。我们可以将字符串 复制一遍,形成一个新的字符串 ,其长度为 。这样做的目的是为了处理环形字符串的情况。

接下来,我们使用一个状态码 来表示当前窗口中 'I'、'o' 和 'x' 出现的次数的奇偶性。具体来说,我们用二进制的三位来表示 'I'、'o' 和 'x' 的出现次数是奇数还是偶数,其中 1 表示奇数,0 表示偶数。例如,状态码 表示当前窗口中 'I' 出现奇数次,'o' 出现偶数次,'x' 出现奇数次。

我们使用一个队列 来维护当前状态码为 时所有可能的最长子串的起始位置。每次遇到一个新的字符时,我们更新状态码 ,并将当前位置 加入到对应的队列 中。同时,我们需要从队列的头部删除那些长度超过 的子串的起始位置,因为它们已经不可能是最长的满足条件的子串了。

最后,我们遍历所有的队列 ,找出其中最长的子串的长度,即为答案。

参考代码

• Python

from collections import deque

def longest_substring(s):
    n = len(s)
    s = s + s  # 将字符串复制一遍,形成环形字符串
    ans = 0
    q = [deque() for _ in range(8)]  # 初始化 8 个队列,用于存储不同状态码下的子串起始位置
    x = 0  # 初始状态码为 0
    q[0].append(-1)  # 将 -1 加入到初始队列中,表示子串的起始位置可以从 0 开始

    for i in range(2 * n):
        if s[i] == 'l':
            x ^= 1  # 更新状态码中 'I' 的位
        elif s[i] == 'o':
            x ^= 2  # 更新状态码中 'o' 的位
        elif s[i] == 'x':
            x ^= 4  # 更新状态码中 'x' 的位

        q[x].append(i)  # 将当前位置加入到对应的队列中