题面描述

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

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

思路

为了找到满足条件的最长子串，我们可以使用滑动窗口（Sliding Window）的方法。具体步骤如下：

1. 滑动窗口的定义：使用两个指针 left 和 right 表示当前窗口的左右边界，初始时都指向字符串的起始位置。
2. 字符计数：使用一个哈希表（数组）记录当前窗口内每个字符出现的次数。
3. 窗口扩展与收缩：
   • 不断移动 right 指针，尝试将新的字符加入窗口。
   • 如果遇到指定不包含的字符，或者当前字符的出现次数超过2次，就需要移动 left 指针，缩小窗口，直到窗口内不再包含不允许的字符且每个字符的出现次数不超过2次。
4. 记录最大长度：在窗口每次有效扩展时，记录当前窗口的长度，并更新最大长度。
5. 特殊情况处理：如果整个字符串都不包含指定字符且每个字符出现次数不超过2次，则最长子串就是整个字符串。

代码分析

以下是具体的代码实现步骤：

1. 输入读取：

   • 读取不允许出现的字符 exclude_char。
   • 读取字符串 s。

2. 初始化：

   • 使用一个大小为256的数组 count 来记录字符的出现次数（假设字符集为ASCII）。
   • 初始化 left 和 right 指针都为0。
   • 初始化 max_length 为0，用于记录满足条件的最长子串长度。

3. 滑动窗口遍历：

   • 遍历字符串 s，移动 right 指针。
   • 对于当前字符：
     • 如果是被排除的字符，则将 left 指针移动到 right + 1，并重置 count 数组。
     • 否则，增加该字符在 count 中的计数。
     • 如果该字符的计数超过2次，则需要移动 left 指针，直到该字符的计数不超过2次。
   • 更新 max_length 为当前窗口的长度与之前记录的最大值中的较大者。

4. 输出结果：

   • 最后输出 max_length。

cpp

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    char exclude_char;
    string s;
    // 读取排除的字符
    cin >> exclude_char;
    // 读取字符串
    cin >> s;

    // 记录字符出现次数，ASCII字符集大小为256
    vector<int> count(256, 0);
    int left = 0;
    int max_length = 0;
    int n = s.length();

    for(int right = 0; right < n; ++right){
        char current = s[right];
        // 如果当前字符是被排除的字符
        if(current == exclude_char){
            // 将left移动到right +1，并重置count数组
            // 因为排除字符不允许出现在子串中
            fill(count.begin(), count.end(), 0);
            left = right +1;
            continue;
        }
        // 增加当前字符的计数
        count[current]++;
        // 如果当前字符的计数超过2，则需要移动left指针
        while(count[current] >2){
            count[s[left]]--;
            left++;
        }
        // 更新最大长度
        max_length = max(max_length, right - left +1);
    }

    cout << max_length;
    return 0;
}

python

def longest_substring(exclude_char, s):
    # 记录字符出现次数
    count = {}
    left = 0
    max_length = 0

    for right in range(len(s)):
        current = s[right]
        
        # 如果当前字符是被排除的字符
        if current == exclude_char:
            # 将左指针移动到right + 1
            count.clear()  # 清空字符计数
            left = right + 1
            continue

        # 增加当前字符的计数
        if current in count:
            count[current] += 1
        else:
            count[current] = 1

        # 如果当前字符的计数超过2，则需要移动left指针
        while count[current] > 2:
            count[s[left]] -= 1
            if count[s[left]] == 0:
                del count[s[left]]  # 删除计数为0的字符
            left += 1

        # 更新最大长度
        max_length = max(max_length, right - left + 1)

    return max_length

# 主程序入口
if __name__ == "__main__":
    # 读取排除的字符
    exclude_char = input().strip()
    # 读取字符串
    s = input().strip()
    
    result = longest_substring(exclude_char, s)
    print(result)

java

import java.util.HashMap;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取排除的字符
        char excludeChar = scanner.next().charAt(0);
        // 读取字符串
        String s = scanner.next();
        
        int result = longestSubstring(excludeChar, s);
        System.out.println(result);
        
        scanner.close();
    }

    public static int longestSubstring(char excludeChar, String s) {
        // 记录字符出现次数
        HashMap<Character, Integer> count = new HashMap<>();
        int left = 0;
        int maxLength = 0;

        for (int right = 0; right < s.length(); right++) {
            char current = s.charAt(right);
            
            // 如果当前字符是被排除的字符
            if (current == excludeChar) {
                // 清空字符计数
                count.clear();
                left = right + 1; // 将左指针移动到right + 1
                continue;
            }

            // 增加当前字符的计数
            count.put(current, count.getOrDefault(current, 0) + 1);

            // 如果当前字符的计数超过2，则需要移动left指针
            while (count.get(current) > 2) {
                char leftChar = s.charAt(left);
                count.put(leftChar, count.get(leftChar) - 1);
                if (count.get(leftChar) == 0) {
                    count.remove(leftChar); // 删除计数为0的字符
                }
                left++;
            }

            // 更新最大长度
            maxLength = Math.max(maxLength, right - left + 1);
        }

        return maxLength;
    }
}

题目内容

给定一个字符串 $s$，找出这样一个子串：

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

请你找出满足该条件的最长子串的长度

输入描述

第一行为：要求不包含的指定字符，为单个字符，取值范围 $[0-9,a-z,A-Z]$

第二行为：字符串 $s$，每个字符范围 $[0-9,a-Z]$ ，长度范围 $[1, 10000]$

输出描述

一个整数，满足条件的最长子串的长度；

如果不存在满足条件的子串，则返回 $0$

样例1

输入

D
ABC132

输出

6

样例2

输入

D
ABACA123D

输出

7