#P3247. 寻找符合要求的最长子串(200分)
-
1000ms
Tried: 119
Accepted: 26
Difficulty: 3
所属公司 :
华为od
寻找符合要求的最长子串(200分)
题面描述
给定一个字符串 s,找出满足以下条件的最长子串:
- 该子串中任意一个字符最多出现 2 次。
- 该子串不包含指定的某个字符。
思路
为了找到满足条件的最长子串,我们可以使用滑动窗口(Sliding Window)的方法。具体步骤如下:
- 滑动窗口的定义:使用两个指针
left和right表示当前窗口的左右边界,初始时都指向字符串的起始位置。 - 字符计数:使用一个哈希表(数组)记录当前窗口内每个字符出现的次数。
- 窗口扩展与收缩:
- 不断移动
right指针,尝试将新的字符加入窗口。 - 如果遇到指定不包含的字符,或者当前字符的出现次数超过2次,就需要移动
left指针,缩小窗口,直到窗口内不再包含不允许的字符且每个字符的出现次数不超过2次。
- 不断移动
- 记录最大长度:在窗口每次有效扩展时,记录当前窗口的长度,并更新最大长度。
- 特殊情况处理:如果整个字符串都不包含指定字符且每个字符出现次数不超过2次,则最长子串就是整个字符串。
代码分析
以下是具体的代码实现步骤:
-
输入读取:
- 读取不允许出现的字符
exclude_char。 - 读取字符串
s。
- 读取不允许出现的字符
-
初始化:
- 使用一个大小为256的数组
count来记录字符的出现次数(假设字符集为ASCII)。 - 初始化
left和right指针都为0。 - 初始化
max_length为0,用于记录满足条件的最长子串长度。
- 使用一个大小为256的数组
-
滑动窗口遍历:
- 遍历字符串
s,移动right指针。 - 对于当前字符:
- 如果是被排除的字符,则将
left指针移动到right + 1,并重置count数组。 - 否则,增加该字符在
count中的计数。 - 如果该字符的计数超过2次,则需要移动
left指针,直到该字符的计数不超过2次。
- 如果是被排除的字符,则将
- 更新
max_length为当前窗口的长度与之前记录的最大值中的较大者。
- 遍历字符串
-
输出结果:
- 最后输出
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,找出这样一个子串:
- 该子串中任意一个字符最多出现 2 次
- 该子串不包含指定某个字符
请你找出满足该条件的最长子串的长度
输入描述
第一行为:要求不包含的指定字符,为单个字符,取值范围 [0−9,a−z,A−Z]
第二行为:字符串 s,每个字符范围 [0−9,a−Z] ,长度范围 [1,10000]
输出描述
一个整数,满足条件的最长子串的长度;
如果不存在满足条件的子串,则返回 0
样例1
输入
D
ABC132
输出
6
样例2
输入
D
ABACA123D
输出
7