2023年华为OD机考真题：寻找符合要求的最长子串

算法刷题1年前 (2023)更新江南白衣

全网最全面的华为OD机试真题汇总，100%原题题库，不需要开会员即可查看全部内容，更多考题请查看真题库。

真题库：https://www.yuque.com/codernav.com/od

题目：寻找符合要求的最长子串
知识点双指针
时间限制：1s 空间限制：256MB 限定语言：不限
题目描述：
给定一个字符串 s ，找出这样一个子串：
1）该子串中的任意一个字符最多出现2次；
2）该子串不包含指定某个字符；
请你找出满足该条件的最长子串的长度。
输入描述：
第一行为要求不包含的指定字符，为单个字符，取值范围[0-9a-zA-Z]
第二行为字符串s，每个字符范围[0-9a-zA-Z]，长度范围[1,10000]
输出描述：
一个整数，满足条件的最长子串的长度；如果不存在满足条件的子串，则返回0
示例1
输入：
D
ABC123
输出：
6
示例2
输入：
D
ABACA123D
输出：
7
解题思路：
使用map对象来统计字符出现的次数。
当出现不包含的字符的时候，清空map
当有字符出现次数到达3次的时候（超过2），对map进行遍历，将出现3次的字符以及它之前的字符全部剔除。

代码实现一：

package com.codernav.demo.hwod.exam;

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

/**
 * @title 寻找符合要求的最长子串
 * @Description 给定一个字符串 s ，找出这样一个子串：
 * 1）该子串中的任意一个字符最多出现2次；
 * 2）该子串不包含指定某个字符；
 * 请你找出满足该条件的最长子串的长度。
 * @Author 开发者导航
 * @website https://codernav.com
 * @date 2023/5/18
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char c = sc.nextLine().charAt(0);
        String s = sc.nextLine();
        int left = 0;   //子串的起始位置
        int max = 0;
        /**
         * key：字符
         * value：字符出现的次数
         */
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char temp = s.charAt(i);
            if (temp == c) {
                map.clear();    //指定字符之前的数据需要清空
                left = i + 1; //指定字符本身不做计数，所以需要+1
                continue;
            }
            map.put(temp, map.getOrDefault(temp, 0) + 1);
            while (map.get(temp) == 3) {     //字符出现第二次之前的字符都需要删除
                char rmStr = s.charAt(left);
                left++;
                map.put(rmStr, map.get(rmStr) - 1);    //起始位置后移，字符个数也需要-1
            }

            max = Math.max(max, i - left + 1);
        }
        System.out.println(max);
    }
}

代码实现二：Java满分实现

package com.codernav.demo.hwod.exam;

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

/**
 * @title 寻找符合要求的最长子串
 * @Description 给定一个字符串 s ，找出这样一个子串：
 * 1）该子串中的任意一个字符最多出现2次；
 * 2）该子串不包含指定某个字符；
 * 请你找出满足该条件的最长子串的长度。
 * @Author 开发者导航
 * @website https://codernav.com
 * @date 2023/5/18
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        char c = scanner.next().charAt(0);
        String s = scanner.next();
        test(c, s);
    }

    private static void test(char c, String s) {
        int l = 0;
        int result = 0;
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char temp = s.charAt(i);
            if (temp == c) {
                map.clear();
                l = i + 1;
                continue;
            }
            map.put(temp, map.getOrDefault(temp, 0) + 1);
            while (map.get(temp) == 3) {
                char rmStr = s.charAt(l);
                l++;
                map.put(rmStr, map.get(rmStr) - 1);
            }
            result = Math.max(result, i - l + 1);
        }
        System.out.println(result);
    }
}