题解

题目难度：中等

知识点：动态规划

分析：

1. 设置一个大小为26*N的二维矩阵存放字母及字母在字符串中出现的位置，26行表示26个字母，N列表示对应字母出现的位置

   vector< vector<int> > vec(26);
    for(int i=0; i<str.size(); ++i) {
        vec[str[i]-'a'].push_back(i);
    }

2. 逐次取出每个字母出现次数的行vec[k]
   2-1 计算当前字母，相邻两个位置移动到一起所需要的次数，存放到m*m的矩阵dp中,dp[0][1]表示当前字母第一次出现移动到第二次出现需要的次数,dp[0][1]=abs(v[1]-v[0])-1

   int n = vec.size();
    vector< vector<int> > dp(n, vector<int>(n, 0));
    for(int i=0; i<n-1; ++i) {
        dp[i][i+1] = abs(vec[i+1] - vec[i]) - 1;
    }

   2-2 最快实现将相同字母排在一起的方法就是从两边往中间靠，dp[i][j]是当前状态，表示第i个数到第j个数移动的次数，那么当前状态只跟dp[i+1][j-1]有关，由于将i位置与j位置移动到一起需要(v[j]-v[i]-1)次，但是由于区间内已经有了移动好的(j-i-1)个字母，所以可以少移动这么多次，固需要减去这个数字,所以动态转移方程可以写作：dp[i][j] = dp[i+1][j-1]+(v[j]-v[i]-1)-(j-i-1)

    for(int j=2; j<n; ++j) {
        for(int i=0; i<n-j; ++i) {
            int row = i, col = i+j;
            dp[row][col] = dp[row+1][col-1] + abs(vec[col] - vec[row]) - (col-row);
        }
    }

   2-3 在这个最小次数满足满足约束条件的前提下，筛选出最大的连续字母的个数

    int Max = 0;
    for(int i=0; i<n; ++i) {
        for(int j=i; j<n; ++j) {
            if (dp[i][j] <= m) {
                Max = max(Max, j-i+1);
            }
        }
    }

3. 比较所有字母的最大连续个数，输出其中的最大值即可

     int Max = 0;
     for(int k=0; k<26; ++k) {
         Max = max(Max, cnt(vec[k]));
     }

   动态规划实现如下：

   #include <iostream>
   #include <stdio.h>
   #include <vector>
   #include <queue>
   #include <algorithm>
   #include <string.h>
   #include <string>
   #include <math.h>
   using namespace std;
   string str; //输入字符串
   int m;    //交换次数
   int cnt(const vector<int>& vec) {
     int n = vec.size();
     vector< vector<int> > dp(n, vector<int>(n, 0));
     for(int i=0; i<n-1; ++i) {
         dp[i][i+1] = abs(vec[i+1] - vec[i]) - 1;
     }
     for(int j=2; j<n; ++j) {
         for(int i=0; i<n-j; ++i) {
             int row = i, col = i+j;
             dp[row][col] = dp[row+1][col-1] + abs(vec[col] - vec[row]) - (col-row);
         }
     }
     int Max = 0;
     for(int i=0; i<n; ++i) {
         for(int j=i; j<n; ++j) {
             if (dp[i][j] <= m) {
                 Max = max(Max, j-i+1);
             }
         }
     }
     return  Max;
   }
   int main()
   {
     cin >> str >> m;
     vector< vector<int> > vec(26);
     for(int i=0; i<str.size(); ++i) {
         vec[str[i]-'a'].push_back(i);
     }
     int Max = 0;
     for(int k=0; k<26; ++k) {
         Max = max(Max, cnt(vec[k]));
     }
     cout << Max << endl;
     return 0;
   }