【华为OD-E卷 - 寻找符合要求的最长子串 100分（python、java、c++、js、c）】
题目
给定一个字符串s，找出这样一个子串：
该子串中任意一个字符最多出现2次 该子串不包含指定某个字符 请你找出满足该条件的最长子串的长度
输入描述
- 第一行为：要求不包含的指定字符，为单个字符，取值范围[0-9a-zA-Z]
第二行为：字符串s，每个字符范围[0-9a-zA-Z]，长度范围[1, 10000]
输出描述
- 一个整数，满足条件的最长子串的长度；
如果不存在满足条件的子串，则返回0
用例
用例一：
输入：
D
ABC132
- 1
- 2
输出：
6
- 1
用例二：
输入：
D
ABACA123D
- 1
- 2
输出：
7
- 1
python解法
- 解题思路：
- 问题描述
给定一个字符串 s 和一个需要排除的字符 exclude_char。
找出字符串中不包含 exclude_char 且满足以下条件的最长子字符串长度：
子字符串中每个字符最多出现两次。
解决方案
使用滑动窗口（双指针）和哈希表来高效地计算满足条件的子字符串长度。
核心思想：
使用两个指针 left 和 right 表示窗口的左右边界。
遍历字符串，动态调整窗口的大小和位置以满足条件。
使用哈希表 char_count 记录当前窗口内每个字符的出现次数。
当窗口内的字符出现次数超过 2 时，收缩窗口（移动 left 指针）直到满足条件。
算法步骤
初始化窗口的左右指针 left 和 right 为 0，max_length 为 0。
遍历字符串：
如果当前字符为 exclude_char：
直接跳过该字符，清空窗口内的字符计数，并将 left 指针移动到当前字符之后。
如果当前字符不是 exclude_char：
将其加入窗口，并更新其计数。
如果窗口内的某个字符出现次数超过 2，则移动 left 指针以收缩窗口，直到条件满足。
更新当前窗口的最大长度。
返回最大长度。
def max_substring_length(s, exclude_char):
# 将需要排除的字符转换为 ASCII 值，便于后续比较
exclude = ord(exclude_char)
# 初始化变量
max_length = 0 # 用于存储最长满足条件的子字符串长度
char_count = {} # 哈希表，记录当前窗口内字符的出现次数
left = 0 # 滑动窗口的左边界
# 遍历字符串，right 为滑动窗口的右边界
for right in range(len(s)):
current_char = s[right]
# 如果当前字符为需要排除的字符
if current_char == exclude_char:
# 将左边界移动到当前字符之后，并清空窗口
left = right + 1
char_count.clear()
continue
# 当前字符计数加 1
char_count[current_char] = char_count.get(current_char, 0) + 1
# 如果当前字符出现次数超过 2，则收缩窗口
while char_count.get(current_char, 0) > 2:
left_char = s[left] # 获取左边界的字符
char_count[left_char] -= 1 # 减少左边界字符的计数
# 如果某字符的计数减少到 0，则从哈希表中删除该字符
if char_count[left_char] == 0:
del char_count[left_char]
# 移动左边界
left += 1
# 更新最长子字符串长度
max_length = max(max_length, right - left + 1)
# 返回最长子字符串长度
return max_length
# 主程序
exclude_char = input().strip() # 输入需要排除的字符
input_string = input().strip() # 输入字符串
# 调用函数并输出结果
print(max_substring_length(input_string, exclude_char))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
java解法
- 解题思路
- 问题描述
给定一个字符串 s 和需要排除的字符 excludeChar。
找出字符串中不包含 excludeChar 且满足以下条件的最长子字符串长度：
子字符串中每个字符最多出现两次。
解决方案
使用滑动窗口技术：
定义窗口的左右边界 left 和 right。
使用哈希表 charCount 记录窗口内每个字符的出现次数。
遍历字符串：
如果当前字符是 excludeChar：
重置窗口：移动 left 指针到当前字符之后，并清空 charCount。
如果当前字符不是 excludeChar：
将其加入窗口，并更新其计数。
如果某字符在窗口内的计数超过 2，则移动 left 指针收缩窗口，直到计数满足条件。
更新当前窗口的最大长度
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 输入需要排除的字符
String excludeChar = sc.nextLine();
// 输入待处理的字符串
String inputString = sc.nextLine();
// 调用方法计算最长子字符串长度
System.out.println(maxSubstringLength(inputString, excludeChar.charAt(0)));
}
/**
* 计算最长满足条件的子字符串长度
* @param s 输入字符串
* @param excludeChar 需要排除的字符
* @return 满足条件的最长子字符串长度
*/
public static int maxSubstringLength(String s, char excludeChar) {
// 记录最长子字符串长度
int maxLength = 0;
// 用于统计当前窗口内每个字符的出现次数
Map<Character, Integer> charCount = new HashMap<>();
// 滑动窗口的左边界
int left = 0;
// 遍历字符串，right 为窗口的右边界
for (int right = 0; right < s.length(); right++) {
char currentChar = s.charAt(right);
// 如果当前字符是需要排除的字符
if (currentChar == excludeChar) {
// 将窗口左边界移动到当前字符之后，并清空计数
left = right + 1;
charCount.clear();
continue;
}
// 将当前字符加入窗口，并更新其计数
charCount.put(currentChar, charCount.getOrDefault(currentChar, 0) + 1);
// 如果当前字符的出现次数超过 2，则收缩窗口
while (charCount.get(currentChar) > 2) {
char leftChar = s.charAt(left); // 获取左边界字符
charCount.put(leftChar, charCount.get(leftChar) - 1); // 减少左边界字符的计数
// 如果某字符的计数为 0，则从哈希表中移除
if (charCount.get(leftChar) == 0) {
charCount.remove(leftChar);
}
// 移动左边界
left++;
}
// 更新最长子字符串长度
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
C++解法
- 解题思路
更新中
- 1
C解法
更新中
- 1
JS解法
给定一个字符串 s 和一个需要排除的字符 excludeChar。
找出不包含 excludeChar 且满足以下条件的最长子字符串长度：
子字符串中每个字符最多出现两次。
解决方案
使用滑动窗口技术和一个哈希表来统计窗口内字符的出现次数。
滑动窗口的核心思想：
定义窗口的左右边界 left 和 right。
遍历字符串，动态调整窗口的大小和位置以满足条件：
如果当前字符是 excludeChar，重置窗口。
如果当前字符不是 excludeChar，更新其计数。
如果某字符在窗口内的计数超过 2，移动 left 指针收缩窗口，直到条件满足。
在每一步中，记录窗口的最大长度
const readline = require("readline");
// 创建输入输出接口
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
// 用于存储输入
const inp = [];
// 处理每行输入
rl.on("line", (line) => {
inp.push(line);
// 当输入的两行都完成时，调用逻辑处理函数
if (inp.length === 2) {
console.log(maxSubstringLength(inp[1], inp[0])); // 调用主逻辑函数
inp.length = 0; // 重置输入存储
}
});
/**
* 计算最长满足条件的子字符串长度
* @param {string} s - 输入字符串
* @param {string} excludeChar - 要排除的字符
* @returns {number} - 返回最长子字符串长度
*/
function maxSubstringLength(s, excludeChar) {
// 将排除的字符转换为 ASCII 编码
const exclude = excludeChar.charCodeAt(0);
// 初始化最长子字符串长度
let maxLength = 0;
// 用于记录当前窗口内字符的出现次数
let charCount = {};
// 滑动窗口的左边界
let left = 0;
// 遍历字符串，右边界为 `right`
for (let right = 0; right < s.length; right++) {
const currentChar = s.charCodeAt(right); // 当前字符的 ASCII 编码
// 如果当前字符是需要排除的字符
if (currentChar === exclude) {
// 将窗口左边界移动到当前字符之后，并清空字符计数
left = right + 1;
charCount = {};
continue;
}
// 将当前字符加入窗口，并更新其计数
charCount[currentChar] = (charCount[currentChar] || 0) + 1;
// 如果当前字符在窗口内的出现次数超过 2，则收缩窗口
while (charCount[currentChar] > 2) {
const leftChar = s.charCodeAt(left); // 获取左边界的字符
charCount[leftChar]--; // 减少左边界字符的计数
left++; // 移动左边界
}
// 更新最长子字符串长度
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
注意：
如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏
评论记录：
回复评论：