E卷-寻找符合要求的最长子串-200p

寻找符合要求的最长子串

问题描述

给定一个字符串 ，要求找出满足以下条件的最长子串：

1. 该子串中任意一个字符最多出现 2 次。
2. 该子串不包含指定的某个字符。

请计算满足上述条件的最长子串的长度。

输入格式

第一行包含一个字符，表示指定不能包含的字符，取值范围为 [0-9a-zA-Z]。

第二行为字符串 ，每个字符的取值范围为 [0-9a-zA-Z]。

输出格式

输出一个整数，表示满足条件的最长子串的长度。如果不存在满足条件的子串，则输出 0。

样例输入1

D
ABC132

样例输出1

6

样例输入2

D
ABACA123D

样例输出2

7

样例解释

数据范围

• 字符串 的长度范围：
• 字符取值范围：[0-9a-zA-Z]

题解

滑动窗口

这道题目可以使用滑动窗口的方法来解决。滑动窗口是一种常用的字符串处理技巧，特别适合处理子串相关的问题。

解题思路如下：

1. 使用两个指针 left 和 right 来表示窗口的左右边界。
2. 用一个哈希表（或者数组）来记录窗口内每个字符出现的次数。
3. 右指针不断向右移动，扩大窗口：
   • 如果遇到指定的不能包含的字符，重置窗口。
   • 如果某个字符出现次数超过 2 次，左指针向右移动，缩小窗口，直到该字符的出现次数不超过 2 次。
4. 在这个过程中，不断更新最长子串的长度。

参考代码

• Python

def longest_valid_substring(exclude_char, s):
    """
    寻找符合要求的最长子串
    
    :param exclude_char: 指定不能包含的字符
    :param s: 输入的字符串
    :return: 最长符合要求的子串长度
    """
    char_count = {}  # 用于记录字符出现次数的字典
    left = 0  # 滑动窗口的左边界
    max_length = 0  # 最长符合要求的子串长度
    
    for right in range(len(s)):
        # 如果遇到指定的不能包含的字符，重置窗口
        if s[right] == exclude_char:
            left = right + 1
            char_count.clear()
            continue
        
        # 更新字符出现次数
        char_count[s[right]] = char_count.get(s[right], 0) + 1
        
        # 如果某个字符出现次数超过2次，移动左指针
        while char_count[s[right]] > 2:
            char_count[s[left]] -= 1
            if char_count[s[left]] == 0:
                del char_count[s[left]]
            left += 1
        
        # 更新最长子串长度
        max_length = max(max_length, right - left + 1)
    
    return max_length

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

# 计算并输出结果
result = longest_valid_substring(exclude_char, s)
print(result)

• C

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

#define MAX_LEN 10001

int longest_valid_substring(char exclude_char, char* s) {
    int char_count[128] = {0};  // 用于记录字符出现次数的数组
    int left = 0;  // 滑动窗口的左边界
    int max_length = 0;  // 最长符合要求的子串长度
    int len = strlen(s);
    
    for (int right = 0; right < len; right++) {
        // 如果遇到指定的不能包含的字符，重置窗口
        if (s[right] == exclude_char) {
            left = right + 1;
            memset(char_count, 0, sizeof(char_count));
            continue;
        }
        
        // 更新字符出现次数
        char_count[s[right]]++;
        
        // 如果某个字符出现次数超过2次，移动左指针
        while (char_count[s[right]] > 2) {
            char_count[s[left]]--;
            left++;
        }
        
        // 更新最长子串长度
        int current_length = right - left + 1;
        if (current_length > max_length) {
            max_length = current_length;
        }
    }
    
    return max_length;
}

int main() {
    char exclude_char;
    char s[MAX_LEN];
    
    scanf("%c", &exclude_char);
    scanf