华为OD机试E卷 - 寻找符合要求的最长子串 （Java & Python& JS & C++ & C ）

https://blog.csdn.net/banxia_frontend/article/details/141831112

最新华为OD机试

真题目录：点击查看目录 华为OD面试真题精选：点击立即查看

题目描述

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

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

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

输入描述

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

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

输出描述

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

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

示例1

输入

D
ABC123

输出

6

说明

无

示例2

输入

D
ABACA123D

输出

7

说明

无

解题思路

题目要求我们从给定的字符串 s 中找出一个满足以下两个条件的最长子串：

1. 任意一个字符最多出现2次： 子串中的每个字符在子串中出现的次数不能超过2次。
2. 子串不包含指定字符： 子串不能包含输入的指定字符。

输出的是满足以上条件的最长子串的长度。如果没有符合条件的子串，则返回0。

示例分析

示例 1

输入：

D
ABC123

输出：

6

分析：

• 排除字符为 D。
• 字符串 s 为 ABC123。
• 整个字符串 ABC123 不包含字符 D，并且每个字符都没有超过2次，因此整个字符串符合条件。
• 满足条件的最长子串为 ABC123，长度为 6。

示例 2

输入：

D
ABACA123D

输出：

7

分析：

• 排除字符为 D。

• 字符串 s 为 ABACA123D。

• 从 s 中找一个最长的子串，该子串：

  1. 不包含字符 D。
  2. 任意一个字符出现次数不超过2次。

• 在字符串 ABACA123D 中，有多个子串不包含 D，但需要满足字符出现次数不超过2次的条件：

  • BACA123 是一个符合条件的子串，每个字符最多出现2次，并且长度为 7。

• 因此，满足条件的最长子串为 BACA123，长度为 7。

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 输入exclude和s
        String exclude = scanner.next();
        String s = scanner.next();

        // 获取要排除的字符
        char excludeChar = exclude.charAt(0);

        // 存储每个字符出现的下标
        Map<Character, List<Integer>> charIndexMap = new HashMap<>();

        // 定义左右指针
        int left = 0, right = 0;

        // 定义最长子串长度
        int maxLength = 0;

        // 遍历字符串
        while (right < s.length()) {
            char currentChar = s.charAt(right);

            // 如果当前字符是要排除的字符
            if (excludeChar == currentChar) {
                // 计算当前有效窗口的长度
                if (right > left) {
                    maxLength = Math.max(maxLength, right - left);
                }
                // 移动指针并清空map，因为新的窗口开始
                right++;
                left = right;
                charIndexMap.clear();
            } else {
                // 如果当前字符不是要排除的字符
                // 处理当前字符的出现次数
                charIndexMap.computeIfAbsent(currentChar, k -> new ArrayList<>());
                List<Integer> charIndexes = charIndexMap.get(currentChar);
                // 如果当前字符的出现次数已经超过2次
                if (charIndexes.size() >= 2) {
                    // 需要移动左指针到当前字符第一次出现的下一个位置
                    int firstOccurrence = charIndexes.get(0);
                    left = Math.max(left, firstOccurrence + 1);
                    // 移除第一次出现的记录
                    charIndexes.remove(0);
                }
                // 将当前字符的下标加入列表
                charIndexes.add(right);
                // 更新当前窗口的最大长度
                maxLength = Math.max(maxLength, right - left + 1);
                // 右指针向后移动
                right++;
            }
        }

        // 输出最长子串长度
        System.out.println(maxLength);
    }
}

Python

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

# 获取要排除的字符
exclude_char = exclude[0]

# 存储字符出现的索引位置
char_index_map = {}

left, right = 0, 0
max_length = 0

while right < len(s):
    current_char = s[right]

    if current_char == exclude_char:
        # 遇到要排除的字符，计算最长子串
        if right > left:
            max_length = max(max_length, right - left)
        # 重新调整指针
        right += 1
        left = right
        char_index_map.clear()
    else:
        # 处理字符的出现情况
        if current_char not in char_index_map:
            char_index_map[current_char] = []

        if len(char_index_map[current_char]) >= 2:
            # 移动左指针
            left = max(left, char_index_map[current_char].pop(0) + 1)

        # 记录字符的位置
        char_index_map[current_char].append(right)

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

print(max_length)

JavaScript

const readline = require('readline');

// 创建读取输入的接口
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

// 读取输入
rl.on('line', (exclude) => {
    rl.on('line', (s) => {
        // 获取要排除的字符
        const excludeChar = exclude.charAt(0);

        // 存储每个字符的出现位置
        let charIndexMap = new Map();

        let left = 0, right = 0;
        let maxLength = 0;

        while (right < s.length) {
            let currentChar = s[right];

            if (currentChar === excludeChar) {
                // 遇到要排除的字符，计算当前最长子串
                if (right > left) {
                    maxLength = Math.max(maxLength, right - left);
                }
                // 移动指针并清空映射表
                right++;
                left = right;
                charIndexMap.clear();
            } else {
                // 不是要排除的字符，处理字符出现的位置
                if (!charIndexMap.has(currentChar)) {
                    charIndexMap.set(currentChar, []);
                }

                let charIndexes = charIndexMap.get(currentChar);
                if (charIndexes.length >= 2) {
                    // 移动左指针到当前字符第一次出现的下一个位置
                    let firstOccurrence = charIndexes.shift();
                    left = Math.max(left, firstOccurrence + 1);
                }

                // 记录当前字符的位置
                charIndexes.push(right);

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

        console.log(maxLength);
        rl.close();
    });
});

C++

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

int main() {
    string exclude, s;
    cin >> exclude >> s;

    // 要排除的字符
    char excludeChar = exclude[0];

    // 存储字符出现的索引位置
    unordered_map<char, vector<int>> charIndexMap;

    int left = 0, right = 0;
    int maxLength = 0;

    while (right < s.length()) {
        char currentChar = s[right];

        if (currentChar == excludeChar) {
            // 遇到要排除的字符，计算当前窗口的最大长度
            if (right > left) {
                maxLength = max(maxLength, right - left);
            }
            // 移动指针并清空字符索引映射
            right++;
            left = right;
            charIndexMap.clear();
        } else {
            // 不是排除字符，处理字符索引
            if (charIndexMap[currentChar].size() >= 2) {
                // 需要移动左指针
                int firstOccurrence = charIndexMap[currentChar][0];
                left = max(left, firstOccurrence + 1);
                charIndexMap[currentChar].erase(charIndexMap[currentChar].begin());
            }

            // 记录字符的位置
            charIndexMap[currentChar].push_back(right);

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

    cout << maxLength << endl;
    return 0;
}

C语言

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

#define MAX_LEN 1000  

int main() {
    char exclude[2], s[MAX_LEN];
    scanf("%s", exclude);
    scanf("%s", s);

    char excludeChar = exclude[0];
    int left = 0, right = 0;
    int maxLength = 0;

    // 存储字符出现的位置，假设字符都是 ASCII 码（0~255）
    int charIndexMap[256][3]; // 只存最多 2 次出现的索引
    memset(charIndexMap, -1, sizeof(charIndexMap));

    while (s[right] != '\0') {
        char currentChar = s[right];

        if (currentChar == excludeChar) {
            // 遇到排除字符，计算当前窗口长度
            if (right > left) {
                if (maxLength < right - left) {
                    maxLength = right - left;
                }
            }
            // 重新调整指针
            right++;
            left = right;
            memset(charIndexMap, -1, sizeof(charIndexMap)); // 清空索引映射
        } else {
            // 处理字符的出现情况
            int *charIndexes = charIndexMap[(int)currentChar];

            // 统计当前字符出现的次数
            if (charIndexes[0] != -1 && charIndexes[1] != -1) {
                // 若已出现2次，移动左指针
                left = (left > charIndexes[0] + 1) ? left : charIndexes[0] + 1;
                // 移除最早的索引
                charIndexes[0] = charIndexes[1];
                charIndexes[1] = -1;
            }

            // 记录新索引
            if (charIndexes[0] == -1) {
                charIndexes[0] = right;
            } else {
                charIndexes[1] = right;
            }

            // 更新最长子串长度
            if (maxLength < right - left + 1) {
                maxLength = right - left + 1;
            }
            right++;
        }
    }

    printf("%d\n", maxLength);
    return 0;
}

完整用例

用例1

D
ABC132

用例2

D
ABACA123D

用例3

A
ABBACDDEE

用例4

Z
ZZZZZZZZ

用例5

a
bbbaaacccc

用例6

E
ABCDEABCDE

用例7

X
ABABACACAX

用例8

B
BACBACBACB

用例9

D
ABCDDCBA

用例10

X
X