第一行两个整数 n , m (1<=m<=n<=50000),第二行为长度为n且只包含’a’和’b’的字符串s。
输出在操作次数不超过 m 的情况下,能够得到的 最大连续 全’a’子串或全’b’子串的长度。
8 1 aabaabaa
5
把第一个 'b' 或者第二个 'b' 置成 'a',可得到长度为 5 的全 'a' 子串。
let [n,m]=readline().split(' ').map(i=>parseInt(i)); let str=readline(); let aPositions=[];//所有a出现的位置,下面类似 let bPositions=[]; for(let i=0;i<str.length;i++){ if(str[i]==='a'){aPositions.push(i);} else{bPositions.push(i);}//字符串里只能有a和b } let result;//准备储存结果 for(let i of [0,1]){ let arr; if(i===0){arr=aPositions;}//考虑把找最长的b的子串 else{arr=bPositions;}//考虑找最长的a的子串 if(m>=arr.length){//这种情况下可以把所有字符全变成a或b result=str.length; break; } for(let i=1;i<arr.length-m;i++){ let temp=arr[i+m]-arr[i-1]-1; result=result>temp?result:temp; } result=result>arr[m]?result:arr[m];//从第一个字符开始去 let toEnd=str.length-1-arr[arr.length-1-m];//到最后一个字符 result=result>toEnd?result:toEnd; } console.log(result);
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e4 + 5;
char y;
int A[maxn], n, K;
string s;
int longestOnes(int K, int x) {
int ans = 0, cnt = 0, idx = 0;
for(int i = 0; i < n; i++) {
if(A[i] == x) cnt++;
else if(K > 0) {
K--;
cnt++;
}
else {
while(A[idx] == x && idx < n) {
idx++;
cnt--;
}
idx++;
}
ans = max(ans, cnt);
}
return ans;
}
int main() {
cin >> n >> K >> s;
for(int i = 0; i < n; i++) A[i] = (s[i] == 'a' ? 1 : 0);
cout << max(longestOnes(K, 1), longestOnes(K, 0)) << endl;
return 0;
}
res = 0 indexa,indexb=[],[] for i in range(n): if string[i]=='a': indexa.append(i) else: indexb.append(i) for i in range(2): if i==0: arrs = indexa else: arrs = indexb if len(arrs)<=m: res = n break for j in range(len(arrs)-m-1): tmp = arrs[j+m+1]-arrs[j]-1 res = max(res,tmp) res = max(res,arrs[m]) res = max(res,n-1-arrs[-(m+1)]) print(res)两种字符的转换可以直接分两种情况讨论,a->b或b->a。先保存下a与b的下标,随后分三种情况讨论:中间段;0到arrs[m];arrs[-(m+1)]到n-1。取三种情况的最大值就是最终结果。
#include<iostream> #include<string> #include<algorithm> using std::string; using std::max; using std::cin; using std::cout; using std::endl; void cin_get(int& sum_num, int& change_num, string& str) { cin >> sum_num; cin >> change_num; cin >> str; //getline(cin, str); } int get_maxlen(string str, int sum_num, int change_num, char c) { string::iterator begin_iter = str.begin(), end_iter = str.begin(); int max_len = 0; int i = 0; while (end_iter != str.end() && i != change_num + 1) { if (*end_iter != c) ++i; ++end_iter; } if (end_iter != str.end()) { --end_iter; max_len = end_iter - begin_iter; } else { return str.size(); } while (end_iter != str.end()) { while (begin_iter != str.end()) { if (*begin_iter == c) ++begin_iter; else { ++begin_iter; break; } } bool is_cheat = false; while (end_iter != str.end()) { if (*end_iter == c) { ++end_iter; } else if (*end_iter != c && !is_cheat) { ++end_iter; is_cheat = true; } else { break; } } max_len = (max_len<(end_iter - begin_iter)) ? (end_iter - begin_iter) : max_len; } return max_len; } int main(int argc, char* argv[]) { int sum_num, change_num; string str; cin_get(sum_num, change_num, str); int a_max = get_maxlen(str, sum_num, change_num, 'a'); int b_max = get_maxlen(str, sum_num, change_num, 'b'); cout << max(a_max, b_max) << endl; return 0; }
temp=arr.get(i+m)-arr.get(i-1)-1;
import java.util.*; public class Main { public static void main(String[] args){ ArrayList<Integer> aindex=new ArrayList<Integer>(); ArrayList<Integer> bindex=new ArrayList<Integer>(); int result=0; Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); char[] str=sc.next().toCharArray(); for(int i=0;i<n;i++) { if(str[i]=='a') aindex.add(i); else bindex.add(i); } if(m>=aindex.size()||m>=bindex.size()){//这种情况下可以把所有字符全变成a或b result=str.length; System.out.println(result); return ; } ArrayList<Integer> arr; for(int j=0;j<=1;j++) { if(j==0) arr=aindex; else arr=bindex; int head=arr.get(m);//从第一个字符开始 int end=str.length-1-arr.get(arr.size()-m-1);//从最后一个字符往前 总串下坐标length-1减去倒数第m+1个空洞的下坐标 result=result>head?result:head; result=result>end?result:end; //计算时,将i与i+m-1分别向左向右移一位 for(int i=1;i+m<arr.size();i++){ //i+m-1 i int temp=arr.get(i+m)-arr.get(i-1)-1; result=result>temp?result:temp; } } System.out.println(result); } }
import sys def isMatch( n,m,s): a=[]#数组记录a,b字符的下标 b=[] for i in range(len(s)): if s[i]=='a': a.append(i) else: b.append(i) res=0 #循环去除a,去除b的情况,保留最优的解 for i in range(2): arr=[] if i==0: arr=a else: arr=b if m>=len(arr): res=len(s) break #挑字符出去有三种情况,第一种,m个"a"(假设把a挑出去)字符在(m+2)个'a'之间, #第二种,m个'a'的前面没有'a'字符存在 #第三种,m个'a'的后面没有'a'字符的存在 #第一种情况 for j in range(len(arr)-m-1): temp=0 temp=arr[j+m+1]-arr[j]-1 res=max(res,temp) #第二种情况 res=max(res,arr[m]) #第三种情况 toend=0 toend=len(s)-1-arr[len(arr)-1-m] res=max(res,toend) print(res) if __name__=='__main__': while True: line=sys.stdin.readline().strip() if line=='': break lines=line.split() a,b=int(lines[0]),int(lines[1]) line=sys.stdin.readline().strip() if line=='': break c=line isMatch(a,b,c)
let [n, m] = readline().split(" ")let str = readline()let mode = str[0];let index = 0;let char_list = new Array;char_list[0] = 0;// 构建ab字符串分段数组,记录每一段的同字符数目// 因为只有两种字符,所以奇数位是一种,偶数位是一种// 算法目的在于找到偶数位之和最大(当中间奇数位之和小于m)或奇数位之和最大(当中间的偶数位之和小于m)for(let i=0; i<str.length; i++){if(str[i]!=mode){index++;char_list[index]=1;mode = str[i];}else{char_list[index]++;}}let sum = function(list){let total =0;for(let i=0; i<list.length; i++){total += list[i]}return total}// 寻找最大组合,从列表尾部开始遍历// list_a,为当前遍历的位(奇数或偶数);list_b,为间隔在list_a中间的位let findMax = function(char_list, list_a, list_b, max_num, m, len){if(len===0){return max_num;}else{list_a.unshift(char_list.pop());len --;while(sum(list_b)>m){list_b.pop();list_a.pop();}sum_num = sum(list_a) + sum(list_b);if(sum_num>max_num){max_num = sum_num;}if(len){list_b.unshift(char_list.pop());len--;return findMax(char_list, list_a, list_b, max_num, m, len);}else{return max_num;}}}len = char_list.length;// 删除数组最后一位,奇、偶对调var char_list_b = char_list.slice(0, len-1);max_a = findMax(char_list, [], [], 0, m, len);max_b = findMax(char_list_b, [], [], 0, m, len-1);// 判断较大的一个,并输出if(max_a > max_b){console.log(max_a);}else{console.log(max_b);}