华为OD-2024年E卷-寻找符合要求的最长子串[200分] -- python

问题描述：

给定一个字符串s，找出这样一个子串:
1)该子串中的任意一个字符最多出现2次;
2)该子串不包含指定某个字符;
请你找出满足该条件的最长子串的长度。
输入描述
第一行为要求不包含的指定字符，为单个字符，取值范围[0-9a-zA-Z]
第二行为字符串s，每个字符范围[0-9a-zA-Z]，长度范围[1,10000]
输出描述
一个整数，满足条件的最长子串的长度;如果不存在满足条件的子串，则返回0

D
ABC123

6

D
ABACA123D

7

解题思路：

限制条件：

1. 不包含指定字符
2. 子串中任意字符出现不超过两次

遍历原字符串的每一个子串，符合条件则更新最大长度，否则下一个，字符串最大长度为

子字符串由起始位置与结束位置确定，如何优化这个过程

优化：

1. 先固定结束位置，也就是只一个for循环遍历结束位置，用left维护起始位置；问题：每次left都会重头开始检查限制条件
2. 用right维护结束位置，两者均初始化为0;符合条件则right+1，否则left+1，处理至target字符时，将两者更新为target索引+1

以示例2为例：

是否符合	T	T	T	T	F	T	T		T
子串	A	AB	ABA	ABAC	ABACA	BACA	BACA1	……	BACA123
left	0	0	0	0	0	1	1		1
right	0	1	2	3	4	4	5		8

代码实现：

仅left单指针：

tar = input()
s = input()
ans = 0
for i in range(len(s)):left = 0if s[i] != tar:while left < i:flag = Truefor j in range(left,i+1):if s[j] == tar or s[left:i+1].count(s[j]) > 2:flag = Falseleft += 1breakif flag:ans = max(ans,i-left+1)break
print(ans)

left、right双指针：

tar = input()
s = input()
ans = 0
left,right = 0,0
while right < len(s):if s[right] != tar:if s[left:right+1].count(s[right]) > 2:#只用检查新增的right位置left += 1#不符合条件，左指针右移else:right += 1#符合条件，右指针右移ans = max(ans,right-left)else:#更新至target字符下一个位置left,right = right+1,right+1
print(ans)