2022 字节跳动秋招笔试
题目
有一个小写字母组成的字符串str，字符串长度为n; 字符串中某些位置可以执行修复操作:将这个位置的字符，替换为a~z中的一个字符; 这个修复操作最多可以执行m次; 现在想知道修复之后，字符串str由相同字符组成的子串最大长度是多少。
输入描述
第一行t(1 ≤t≤100)， 表示接下来有t个样例;
每个样例有三行;
第一行是整数n和m,分别表示字符串长度和最多操作次数; (1≤n≤2000,0≤m≤2000)
第二行是字符串str;
第三行是长度为n的01字符串，'0'表示该位置的字符无法修改，'1'表示该位置的字符可以修改;
输出描述
每个样例一行，输出修复之后由相同字符组成的字串最大长度；
//输入
3
5 2
abcda
01110
7 2
abbaccb
1001001
3 0
aab
101
//输出
3
4
2
//样例解释
样例1，可以修复为aaada，相同字符组成的子串最大长度是aaa，长度为3；
样例2，可以修复为abbcccc，相同字符组成的子串最大长度是cccc，长度为4；
样例3，修复次数为0.相同字符组成的子串最大长度是aa，长度为2；
代码
//运行环境 vscode node.js
let readlineSync = require('readline-sync');
readlineSync.setDefaultOptions({ prompt: '' })
let readline = readlineSync.prompt
let process = (n, mm, str, nums) => {
let res = 0;
for (let i = 0; i < n; i++) {
let right = i;
let m = mm;
if (nums[i] === 0) {
while (right < n) {
if (nums[right] === 1) {
if(m === 0 && str[right] !== str[i]) break; //次数用完无法修改
if(m > 0 && str[right] !== str[i]) m--;//将当前字符修改为不可变字符
right++;
} else if (nums[right] === 0) {
if (str[right] !== str[i]) {
break; //后面的不可修改字符与第一个不可修改字符不同
}
right++;
}
}
} else if (nums[i] === 1) {
while (right < n - 1 && nums[right + 1] === 1) {
right++;
}
let firstZero = str[right + 1];//找到从i往后的第一个不可修改字符
right = i;//重新从i位置开始往后找
while (right < n) {
if (nums[right] === 1) {
if(m === 0 && str[right] !== firstZero) break; //次数用完无法修改
if(m > 0 && str[right] !== firstZero) m--;//将当前字符修改为不可变字符
right++;//当前字符与不可修改字符相同，不用浪费m
} else if (nums[right] === 0) {
if (str[right] !== firstZero) {
break; //后面的不可修改字符与第一个不可修改字符不同
}
right++;
}
}
}
res = Math.max(res, right - i);
}
return res;
}
let t = parseInt(readline());
while (t--) {
let inputs = readline().split(" ");
let n = parseInt(inputs[0]);
let m = parseInt(inputs[1]);
let str = readline();
let arr = readline();
let nums = [];
for (let c of arr) {
nums.push(parseInt(c));
}
let res = process(n, m, str, nums);
console.log(res);
}
运行结果
//测试的7组数据
7
5 2
abcda
01110
7 2
abbaccb
1001001
3 0
aab
101
6 2
abccde
010110
6 2
aabccb
110110
5 2
aaacc
11011
3 1
aab
011
//每组数据结果
3
4
2
4
4
5
3
如有错误，欢迎指正~
