2022 字節(jié)跳動(dòng)秋招筆試

題目

有一個(gè)小寫字母組成的字符串str，字符串長(zhǎng)度為n; 字符串中某些位置可以執(zhí)行修復(fù)操作:將這個(gè)位置的字符，替換為a~z中的一個(gè)字符; 這個(gè)修復(fù)操作最多可以執(zhí)行m次; 現(xiàn)在想知道修復(fù)之后，字符串str由相同字符組成的子串最大長(zhǎng)度是多少。

輸入描述

第一行t(1 ≤t≤100)， 表示接下來(lái)有t個(gè)樣例;
每個(gè)樣例有三行;
第一行是整數(shù)n和m,分別表示字符串長(zhǎng)度和最多操作次數(shù); (1≤n≤2000,0≤m≤2000)
第二行是字符串str;
第三行是長(zhǎng)度為n的01字符串，'0'表示該位置的字符無(wú)法修改，'1'表示該位置的字符可以修改;

輸出描述

每個(gè)樣例一行，輸出修復(fù)之后由相同字符組成的字串最大長(zhǎng)度；

//輸入
3
5 2
abcda
01110
7 2
abbaccb
1001001
3 0
aab
101

//輸出
3
4
2

//樣例解釋
樣例1，可以修復(fù)為aaada，相同字符組成的子串最大長(zhǎng)度是aaa，長(zhǎng)度為3；
樣例2，可以修復(fù)為abbcccc，相同字符組成的子串最大長(zhǎng)度是cccc，長(zhǎng)度為4；
樣例3，修復(fù)次數(shù)為0.相同字符組成的子串最大長(zhǎng)度是aa，長(zhǎng)度為2；

代碼

//運(yùn)行環(huán)境 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; //次數(shù)用完無(wú)法修改
                    if(m > 0  && str[right] !== str[i]) m--;//將當(dāng)前字符修改為不可變字符
                    right++;
                } else if (nums[right] === 0) {
                    if (str[right] !== str[i]) {
                        break; //后面的不可修改字符與第一個(gè)不可修改字符不同
                    }
                    right++;
                }
            }
        } else if (nums[i] === 1) {
            while (right < n - 1 && nums[right + 1] === 1) {
                right++;
            }
            let firstZero = str[right + 1];//找到從i往后的第一個(gè)不可修改字符
            right = i;//重新從i位置開始往后找
            while (right < n) {
                if (nums[right] === 1) {
                    if(m === 0 && str[right] !== firstZero) break; //次數(shù)用完無(wú)法修改
                    if(m > 0  && str[right] !== firstZero) m--;//將當(dāng)前字符修改為不可變字符
                    right++;//當(dāng)前字符與不可修改字符相同，不用浪費(fèi)m
                } else if (nums[right] === 0) {
                    if (str[right] !== firstZero) {
                        break; //后面的不可修改字符與第一個(gè)不可修改字符不同
                    }
                    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);
}

運(yùn)行結(jié)果

//測(cè)試的7組數(shù)據(jù)
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

//每組數(shù)據(jù)結(jié)果
3
4
2
4
4
5
3

如有錯(cuò)誤，歡迎指正~