参考:https://blog.csdn.net/cxzzxc123456/article/details/79058419
【编码题】字符串S由小写字母构成,长度为n。定义一种操作,每次都可以挑选字符串中任意的两个相邻字母进行交换。询问在至多交换m次之后,字符串中最多有多少个连续的位置上的字母相同?
输入描述:
第一行为一个字符串S与一个非负整数m。(1 <= |S| <= 1000, 1 <= m <= 1000000)
输出描述:
一个非负整数,表示操作之后,连续最长的相同字母数量。
输入例子1:
abcbaa 2
输出例子1:
2
实现:
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <climits>
using namespace std;
int dp(int i, int j, vector<int>& locations) {
if (i == j) return 0;
else if (i + 1 == j) return locations[j] - locations[i] - 1;
else return dp(i + 1, j - 1, locations) + locations[j] - locations[i] - (j - i);
}
int helpSeq(string& s, int m) {
int n = s.size();
vector<vector<int> > v(n, vector<int>(26, 0));
for (int i = 0; i < n; i++) {
v[i][s[i] - 'a'] = 1;
}
vector<int> num(26, 0);
for (int j = 0; j < 26;j++) {
vector<int> locations(n, 0);
int k = 0;
for (int i = 0; i < n; i++) {
if (v[i][j] == 1) {
locations[k++] = i;
}
}
if (k == 0) num[j] = 1;
else {
int temp = INT_MIN;
for (int i = 0; i < k; i++) {
for (int ii = i; ii < k; ii++) {
int re = dp(i, ii, locations);
if (re <= m) {
if (ii - i + 1 > temp) temp = ii - i + 1;
}
}
}
num[j] = temp;
}
}
int sum = num[0];
for (int i = 1; i < 26; i++) {
if (sum < num[i]) sum = num[i];
}
return sum;
}
int main() {
string s;
int m;
cin >> s;
cin >> m;
int res = helpSeq(s, m);
cout << res << endl;
return 0;
}