E卷-刷题笔记合集🔗

最长子字符串的长度

问题描述

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  # 更新状态码中 'l' 的位
        elif s[i] == 'o':
            x ^= 2  # 更新状态码中 'o' 的位
        elif s[i] == 'x':
            x ^= 4  # 更新状态码中 'x' 的位

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

        # 从队列头部删除长度超过 n 的子串的起始位置
        while q[x][-1] - q[x][0] > n:
            q[x].popleft()

        ans = max(ans, q[x][-1] - q[x][0])  # 更新最长子串的长度

    return ans

# 读取输入
s = input().strip()

# 调用函数并输出结果
print(longest_substring(s))

• C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_N 500000

// 定义队列结构
typedef struct {
    int* data;
    int front;
    int rear;
    int size;
} Queue;

// 初始化队列
void initQueue(Queue* q, int capacity) {
    q->data = (int*)malloc(sizeof(int) * capacity);
    q->front = q->rear = 0;
    q->size = capacity;
}

// 入队
void enqueue(Queue* q, int value) {
    q->data[q->rear] = value;
    q->rear = (q->rear + 1) % q->size;
}

// 出队
int dequeue(Queue* q) {
    int value = q->data[q->front];
    q->front = (q->front + 1) % q->size;
    return value;
}

// 获取队首元素
int front(Queue* q) {
    return q->data[q->front];
}

// 获取队尾元素
int back(Queue* q) {
    return q->data[(q->rear - 1 + q->size) % q->size];
}

// 判断队列是否为空
int isEmpty(Queue* q) {
    return q->front == q->rear;
}

int longest_substring(char* s) {
    int n = strlen(s);
    char* t = (char*)malloc(sizeof(char) * (2 * n + 1));
    strcpy(t, s);
    strcat(t, s);  // 将字符串复制一遍，形成环形字符串

    int ans = 0;
    Queue q[8];
    for (int i = 0; i < 8; i++) {
        initQueue(&q[i], 2 * n + 1);
    }

    int x = 0;  // 初始状态码为 0
    enqueue(&q[0