- 寻找符合要求的最长子串（Java JS Python）)
(200分)- 寻找符合要求的最长子串（Java & JS & Python）
题目描述
给定一个字符串s，找出这样一个子串：
- 该子串中任意一个字符最多出现2次
- 该子串不包含指定某个字符
请你找出满足该条件的最长子串的长度
输入描述
第一行为：要求不包含的指定字符，为单个字符，取值范围[0-9a-zA-Z]
第二行为：字符串s，每个字符范围[0-9a-zA-Z]，长度范围[1, 10000]
输出描述
一个整数，满足条件的最长子串的长度；
如果不存在满足条件的子串，则返回0
用例
| 输入 | D ABC132 |
| 输出 | 6 |
| 说明 | 无 |
| 输入 | D ABACA123D |
| 输出 | 7 |
| 说明 | 无 |
题目解析
简单的滑窗应用。
我们以用例2画图解释：
由于本题描述中说：字符串s，每个字符范围[0-9a-zA-Z]，以及屏蔽字符取值范围[0-9a-zA-Z]，因此我们统计滑窗内部字符数量时，可以使用长度为128的数组来作为容器，因为要统计的字符的ASCII码必然在0~128范围中。
JavaScript算法源码
/* JavaScript Node ACM模式 控制台输入获取 */ const readline = require("readline"); const rl = readline.createInterface({ input: process.stdin, output: process.stdout, }); const lines = []; rl.on("line", (line) => { lines.push(line); if (lines.length === 2) { console.log(getResult(lines[1], lines[0])); lines.length = 0; } }); /** * @param {*} s 字符串s * @param {*} ex 要求不包含的指定字符 * @returns 满足条件的最长子串的长度 */ function getResult(s, ex) { ex = ex.charCodeAt(); const count = new Array(128).fill(0); let l = 0; // 滑窗左边界 let r = 0; // 滑窗右边界 let ans = 0; // 记录满足条件的最长子串的长度 // 滑窗右边界不越界的话，可以继续右移 while (r < s.length) { // r指针指向的字符是滑窗新增的字符 const add_c = s[r].charCodeAt(); if (ex == add_c) { // 如果新增字符是屏蔽字符，那么滑窗不能包含此字符，为了让滑窗不能包含此字符，只能让滑窗的左边界l移动到此字符的右边一个位置 ans = Math.max(ans, r - l); // 但是在具体移动之前，需要将上一个状态的滑窗长度，和统计的最大长度进行比较，保留最大的 l = ++r; // 滑窗左边界l要移动到屏蔽字符的右边，即r+1位置，而滑窗的右边界r又不能落后于左边界l，因此相当于同时移动 count.fill(0); // 此时滑窗为空，因此清空统计的字符的数量 } else { // 如果新增字符不是屏蔽字符，那么就纳入滑窗 count[add_c]++; // 如果此时新增字符的数量超过了2，那么我们应该让滑窗的左边界l右移，直到该新增字符的数量等于2时停止 if (count[add_c] > 2) { ans = Math.max(ans, r - l); // 但是在具体移动之前，我们需要将上一个状态的滑窗长度，和统计的最大长度进行比较，保留最大的 } while (count[add_c] > 2) { const remove_c = s[l].charCodeAt(); count[remove_c]--; l++; } r++; } } return Math.max(ans, r - l); // 对最后一次滑窗位置进行记录 }Java算法源码
import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String exclude = sc.next(); String s = sc.next(); System.out.println(getResult(s, exclude.charAt(0))); } public static int getResult(String s, char ex) { // 记录滑窗内部每个字符出现的次数 int[] count = new int[128]; // 滑窗左边界,右边界 int l = 0, r = 0; // 记录满足条件的最长子串的长度 int ans = 0; // 滑窗右边界不越界的话，可以继续右移 while (r < s.length()) { // r指针指向的字符是滑窗新增的字符 char add_c = s.charAt(r); if (ex == add_c) { // 如果新增字符是屏蔽字符，那么滑窗不能包含此字符，为了让滑窗不能包含此字符，只能让滑窗的左边界l移动到此字符的右边一个位置 ans = Math.max(ans, r - l); // 但是在具体移动之前，需要将上一个状态的滑窗长度，和统计的最大长度进行比较，保留最大的 l = ++r; // 滑窗左边界l要移动到屏蔽字符的右边，即r+1位置，而滑窗的右边界r又不能落后于左边界l，因此相当于同时移动 Arrays.fill(count, 0); // 此时滑窗为空，因此清空统计的字符的数量 } else { // 如果新增字符不是屏蔽字符，那么就纳入滑窗 count[add_c]++; // 如果此时新增字符的数量超过了2，那么我们应该让滑窗的左边界l右移，直到该新增字符的数量等于2时停止 if (count[add_c] > 2) { ans = Math.max(ans, r - l); // 但是在具体移动之前，我们需要将上一个状态的滑窗长度，和统计的最大长度进行比较，保留最大的 } while (count[add_c] > 2) { char remove_c = s.charAt(l); count[remove_c]--; l++; } r++; } } return Math.max(ans, r - l); // 对最后一次滑窗位置进行记录 } }Python算法源码
# 输入获取 ex = ord(input()) # 要求不包含的指定字符 s = input() # 字符串s # 算法入口 def getResult(): # 记录滑窗内部每个字符出现的次数 count = [0]*128 l = 0 # 滑窗左边界 r = 0 # 滑窗右边界 ans = 0 # 记录满足条件的最长子串的长度 # 滑窗右边界不越界的话，可以继续右移 while r < len(s): # r指针指向的字符是滑窗新增的字符 add_c = ord(s[r]) if ex == add_c: # 如果新增字符是屏蔽字符，那么滑窗不能包含此字符，为了让滑窗不能包含此字符，只能让滑窗的左边界l移动到此字符的右边一个位置 ans = max(ans, r - l) # 但是在具体移动之前，需要将上一个状态的滑窗长度，和统计的最大长度进行比较，保留最大的 r += 1 # 滑窗左边界l要移动到屏蔽字符的右边，即r+1位置，而滑窗的右边界r又不能落后于左边界l，因此相当于同时移动 l = r count = [0]*128 # 时滑窗为空，因此清空统计的字符的数量 else: # 如果新增字符c是目标子串可以包含的字符 count[add_c] += 1 # 那么就纳入滑窗 if count[add_c] > 2: # 如果此时新增字符的数量超过了2，那么我们应该让滑窗的左边界l右移，直到该新增字符的数量等于2时停止 ans = max(ans, r - l) # 但是在具体移动之前，我们需要将上一个状态的滑窗长度，和统计的最大长度进行比较，保留最大的 while count[add_c] > 2: remove_c = ord(s[l]) count[remove_c] -= 1 l += 1 r += 1 # 对最后一次滑窗位置进行记录 return max(ans, r - l) # 算法调用 print(getResult())
)
