题目:
给你一个字符串s,可以将任意一个字符转为任意一个小写字符,这个操作可有m次,问转化后的字符串中最长的相等子串长度。
案例:
s="abcdac" ,m=2,2次操作,可以转化为"abcccc" ,最长是4,返回4。
分析:
题目很好理解,但是如果对算法掌握不是很透彻或者是对滑动窗口、双指针算法学的不是很明白的同学还是有点难度的。字符串的任意字符都可以改变成其他的字符。我们优先考虑滑动窗口双指针来写
定义left和right为左右指针,定义一个字典mp
来记录字符串中每个字符出现的次数。遍历一次字符串s,每次循环执行如下,将该下标元素对应的字符+1,如果right-left+1(现在窗口的长度)- mp字典中最大的数(max_value)> m ,说明不可能完成这样的操作,减去当前mp下标元素对应的字符,left+1。再一次执行right-left+1(现在窗口的长度)- mp字典中最大的数(max_value)> m的操作,直接此判断语句不符合。结束后说明right-left+1的字符串满足操作m次将任意一个字符转为任意一个小写字符。与max_length比较取最大值。
mp:保证是字符串s滑动窗口 [left,right] 中字符对应的字符数量
max_value:滑动窗口中字符数量的最大值
max_length:m次操作后最长的相等子串长度文章来源:https://www.toymoban.com/news/detail-567438.html
题目代码:文章来源地址https://www.toymoban.com/news/detail-567438.html
#include<iostream>
#include<unordered_map>
using namespace std;
int main()
{
string s;
int m;
cin>>s;
cin>>m;
unordered_map<char,int>mp;
int left=0;
int max_lenth=0;
for(int right=0;right<s.size();right++)
{
mp[s[right]]++;
int max_value=0;
for(int i=0;i<26;i++)
{
char ch='a'+i;
max_value=max(max_value,mp[ch]);
}
while(right-left+1-max_value>m)
{
mp[s[left]]--;
left++;
}
max_lenth=max(max_lenth,right-left+1);
}
cout<<max_lenth<<endl;
}
到了这里,关于分享一道字节跳动后端面试算法题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!