2023-01-06：给定一个只由小写字母组成的字符串str，长度为N，
给定一个只由0、1组成的数组arr，长度为N，
arr[i]等于 0 表示str中i位置的字符不许修改，
arr[i] 等于 1表示str中i位置的字符允许修改，
给定一个正数m，表示在任意允许修改的位置，
可以把该位置的字符变成a~z中的任何一个，
可以修改m次。
返回在最多修改m次的情况下，全是一种字符的最长子串是多长。
1 <= N, M <= 10^5，
所有字符都是小写。
来自字节。
答案2023-01-06：
尝试全变成a一直到全变成z，遍历26次。每次滑动窗口。
时间复杂度：O(N)。
空间复杂度：O(1)。
代码用rust和solidity编写。
代码用rust编写。代码如下：
代码语言：javascript复制use rand::Rng;
use std::{iter::repeat, vec};
fn main() {
let str = "bbbcdbcade";
let mut arr = vec![1, 1, 0, 1, 0, 1, 0, 0, 1, 0];
let m = 4;
let ans = max_len2(&str, &mut arr, m);
println!("ans = {}", ans);
let nn: i32 = 100;
let rr: i32 = 5;
let test_time: i32 = 5000;
println!("测试开始");
for i in 0..test_time {
let n = rand::thread_rng().gen_range(0, nn) 1;
let m = rand::thread_rng().gen_range(0, n) 1;
let str = random_string(n, rr);
let mut arr = random_array(n);
let ans1 = max_len1(&str, &mut arr, m);
let ans2 = max_len2(&str, &mut arr, m);
if ans1 != ans2 {
println!("出错了!{}", i);
println!("str = {}", str);
println!("arr = {:?}", arr);
println!("m = {}", m);
println!("ans1 = {}", ans1);
println!("ans2 = {}", ans2);
break;
}
}
println!("测试结束");
}
// 暴力方法
// 为了测试
fn max_len1(str1: &str, arr: &mut Vec<i32>, m: i32) -> i32 {
let s = str1.as_bytes();
let n = s.len() as i32;
let mut ans = 0;
for c in 'a' as u8..='z' as u8 {
for i in 0..n {
let mut j = n - 1;
while j >= i {
if ok(s, i, j, c, arr, m) {
ans = get_max(ans, j - i 1);
break;
}
j -= 1;
}
}
}
return ans;
}
// 为了测试
fn ok(s: &[u8], l: i32, r: i32, c: u8, arr: &mut Vec<i32>, mut m: i32) -> bool {
for i in l..=r {
if s[i as usize] == c {
continue;
}
if arr[i as usize] == 0 || m == 0 {
return false;
}
m -= 1;
}
return true;
}
// 正式方法
fn max_len2(str1: &str, arr: &mut Vec<i32>, m: i32) -> i32 {
let s = str1.as_bytes();
let n = s.len() as i32;
let mut ans = 0;
for aim in 'a' as u8..='z' as u8 {
// 右边界
// [l..r)
let mut r = 0;
// 用了几次修改了
// change == m 用完的时候
let mut change = 0;
for l in 0..n {
// l......r ->
while r < n {
if s[r as usize] == aim {
r = 1;
continue;
}
// s[r] != aim
if arr[r as usize] == 0 || change == m {
break;
}
// s[r] != aim && arr[r] == 1 && change < m
change = 1;
r = 1;
}
// l....r-1 r
// X l 1
ans = get_max(ans, r - l);
if s[l as usize] != aim && arr[l as usize] == 1 {
change -= 1;
}
// r r
// l l
// X
r = get_max(r, l 1);
}
}
return ans;
}
fn get_max<T: Clone Copy std::cmp::PartialOrd>(a: T, b: T) -> T {
if a > b {
a
} else {
b
}
}
// 为了测试
fn random_string(n: i32, r: i32) -> String {
let mut arr = String::new();
for _i in 0..n {
arr.push((rand::thread_rng().gen_range(0, r) as u8 'a' as u8) as char);
}
return arr;
}
// 为了测试
fn random_array(n: i32) -> Vec<i32> {
let mut arr: Vec<i32> = vec![];
for _i in 0..n {
arr.push(rand::thread_rng().gen_range(0, 2));
}
return arr;
}
代码用solidity编写。代码如下：
代码语言：javascript复制// SPDX-License-Identifier: MIT
pragma solidity ^0.8.17;
contract Hello{
function main() public pure returns (int32){
bytes memory s = "bbbcdbcade";
int32[] memory arr = new int32[](10);
arr[0] = 1;
arr[1] = 1;
arr[2] = 0;
arr[3] = 1;
arr[4] = 0;
arr[5] = 1;
arr[6] = 0;
arr[7] = 0;
arr[8] = 1;
arr[9] = 0;
int32 m = 4;
return maxLen2(s,arr,m);
}
// 正式方法
function maxLen2(bytes memory s, int32[] memory arr, int32 m) public pure returns (int32){
int32 n = int32(int(s.length));
int32 ans = 0;
for (bytes1 aim = 'a'; aim <='z'; aim = bytes1(uint8(aim) 1)) {
// 右边界
// [l..r)
int32 r = 0;
// 用了几次修改了
// change == m 用完的时候
int32 change = 0;
for (int32 l = 0; l < n; l ) {
// l......r ->
while (r < n) {
if (s[uint32(r)] == aim) {
r ;
continue;
}
// s[r] != aim
if (arr[uint32(r)] == 0 || change == m) {
break;
}
// s[r] != aim && arr[r] == 1 && change < m
change ;
r ;
}
// l....r-1 r
// X l 1
ans = getMax(ans, r - l);
if (s[uint32(l)] != aim && arr[uint32(l)] == 1) {
change--;
}
// r r
// l l
// X
r = getMax(r, l 1);
}
}
return ans;
}
function getMax(int32 a,int32 b) public pure returns (int32){
if(a>b){
return a;
}else{
return b;
}
}
}
