字母交换--字符串dp

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <queue>
using namespace std;
#define int long long
const int N = 200010;
int n,k;
string s;
vector<int>vec[30];
int f[1010][1010];

int cal(vector<int> vec)
{
    
	int n=vec.size();
	memset(f,0,sizeof f);
	
	for(int i=0;i+1<n;i++)
		f[i][i+1]=vec[i+1]-vec[i]-1;
	
	for(int i=2;i<n;i++)
	{
    
		for(int j=0;j+i<n;j++)
		{
    
			int l=j,r=j+i;
			f[l][r]=f[l+1][r-1]+abs(vec[r]-vec[l])-(r-l);
		}
	}
	int res=0;
	for(int i=0;i<n;i++)
		for(int j=i+1;j<n;j++)
			if(f[i][j]<=k)res=max(j-i+1,res);
	return res;
}
signed main()
{
    
	cin>>s>>k;
	for(int i=0;i<s.size();i++)
		vec[s[i]-'a'].push_back(i);
	
	int res=0;
	for(int i=0;i<26;i++)res=max(res,cal(vec[i]));
	cout<<res<<'\n';
}