描述

题目描述

给定我们一个字符串，和一个我们最多可以删除的字母的数量，问我们压缩后的最小长度为多少

压缩规则：

1. 只有一个字符，我们不需要写这个字符的数量
2. 当我们可以删除字母的数量不为$00$的时候，我们可以选择任意删除多少只要最后压缩后得到的字符串长度最小
3. 字符串中只含有小写字母

样例解释

样例输入："aabcccccaaa",1

我们先写出我们压缩后的字符串是什么 $a2bc4a3a2bc4a3$

然后我们可以删除一个字符，我们可以发现我们删除$a,b,ca,b,c$都不会对我们最后的字符串造成任何的影响，所以我们最优的选择就是删除$bb$

所以我们删除之后，我们最后的压缩过后的字符串就是 $a2c4a3a2c4a3$

所以我们最后压缩后的字符串的最小长度为 $66$

所以我们的输出是 6

题解

解法一：DFS + 记忆化

解题思路

首先我们想一下，这个问题可以怎么简化一下，其实我们最多可以删掉$kk$个元素的话，其实我们可以很容易的想明白这件事情，就是我们一定是删了之后的结果是更优的，那么我们的问题其实就是可以转换成为了我们要找到一个长度为$s\mathrm{.}size()-ks.size()\; -\; k$经过压缩后最长的一个子序列

然后我们可以考虑一下，什么样子的比较短，如果我们前面有一个序列假设是$xx$的连续，然后我们中间间隔了一个$bb$，紧接着后面又是连续的一个$xx$的序列，那么我们删除$bb$之后形成的这个序列是目前来看的最优策略，那么我们的问题其实就是又一次的转换了，其实就是求取左半部分就是连续的某一个字符，右半部分是以非左半部分字符开头的一个子序列，然后两段的长度加在一起，然后进行压缩，得到一个值，跟最小值做比较，最后得到最后的最小值

然后我们的右半部分怎么处理，我们右半部分其实还是可以分成一个连续的字符作为左边，然后右边还是以非左半部分字符开头的一个子序列，这样我们发现这个其实是可以用递归求解，然后为了优化，我们直接$DFSDFS$，看到很多小伙伴可能会$TLETLE$，这里我们可以记录一个从一个下表开始在长度为某一个值，压缩之后最短的子序列

代码实现

class Solution {
    int vis[101][101];
//     我们记录从某一个点开始，一定长度的最短子序列
public:
    void init() {
        memset(vis, 0, sizeof vis);
    }
//     初始化
    int count(int n) {
        if (n == 1) return 1;
        if (n < 10) return 2;
        if (n < 100) return 3;
        return 4;
    }
//     获得我们的长度占位，因为最长也就是100，如果是100直接就是4
    int dfs(string s, int idx, int cnt) {
        if (cnt == 0) return 0;
//         子序列的长度变成了0，返回0
        if (idx == s.size()) return INT_MAX;
//         越界了，返回一个极限值
        if (vis[idx][cnt]) return vis[idx][cnt];
//         如果以前已经求出来过这个点，我们可以直接使用，不用重复计算了
        int minn = INT_MAX;
//         我们的最小值
        bitset<26> bt = 0;
//         标记我们处理过的作为开头的字母
        for (int i = idx; i < s.size(); i++) {
            if (bt[s[i] - 'a']) continue;
//             处理过这个字母，不计算
            if (idx > 0 and s[i] == s[idx - 1]) continue;
//             和我们上次操作一样，不计算
            bt[s[i] - 'a'] = 1;
//             标记我们已经使用了
            int len = 0;
//             左半部分的长度
            for (int j = i; j < s.size(); j++) {
                if (s[j] != s[i]) continue;
//                 如果不一样，那他不符合我们之前讲的找左边全都是连着的一个字符的序列
                ++len;
//                 左半部分长度 +1
                if (cnt - len < 0) break;
//                 如果我们左半部分的长度已经大于了我们整个可以使用的子序列的长度，直接挑出去
                int left = count(len);
//                 算一下有多少个，压缩之后是多少
                int right = dfs(s, j + 1, cnt - len);
//                 递归寻找右半部分，然后右半部分又继续拆分
                if (right == INT_MAX) continue;
//                 如果返回的是极限的值，说明是不符合条件，直接跳过
                int allLength = left + right;
//                 我们的总距离就是我们做班服分加上右半部分
                minn = min(minn, allLength);
//                 求一个最小值
            }
        }
        vis[idx][cnt] = minn;
//         标记从idx开始的子序列长度为cnt的子序列最小值
        return minn;
//         返回我们的最小值
    }
    int compressString(string s, int k) {
        init();    
        return dfs(s, 0, s.size() - k);
//         在s中从0开始找长度为s.size() - k的子序列
    }
};

时空复杂度分析

时间复杂度： $O(k\ast n^2)O(k\; *\; n\; ^\; 2)$

理由如下：我们最多删除$kk$个点，查找$kk$次，然后我们每次在递归的过程中是两层的$forfor$循环

空间复杂度： $O(n\ast n)O(n\; *\; n)$

理由如下：我们主要的空间是开在了存储记忆化的状态上，我们记录字母的用$bitsetbitset$优化了

解法二：动态规划

解题思路

首先思想跟我们上面是差不多的，我们要找到一个长度为$s\mathrm{.}size()-ks.size()\; -\; k$经过压缩后最长的一个子序列，然后这里我们定义一下我们的$DPDP$方程

首先我们思考如果我们到了第$ii$位的时候有几种情况

1. 我们删除第$ii$位，也就是说我们第$ii$位和我们的第$i-1i\; -\; 1$位的区别就是增加了一个删除的操作所以这里的状态转移方程就是$dp[i][j+1]=dp[i-1][j]dp[i][j\; +\; 1]\; =\; dp[i\; -\; 1][j]$，这里为了跟代码对应
2. 我们不删除第$ii$位，然后这里的思路跟我们上面的思路是一致的，我们向后寻找和当前的第$ii$位的字符一样的，如果不一样说明我们要删掉这个字符，一样说明我们压缩过后需要后面跟的位数，也就是说我们到了第$mm$位的时候，我们可以得到这么一个状态转移方程$dp[m][j+\mathrm{不}\mathrm{同}\mathrm{的}]=min(dp[m][j+\mathrm{不}\mathrm{同}\mathrm{的}],\mathrm{压}\mathrm{缩}\mathrm{过}\mathrm{的}\mathrm{相}\mathrm{同}\mathrm{的}\mathrm{字}\mathrm{符}\mathrm{串}\mathrm{的}\mathrm{长}\mathrm{度}+dp[i-1][j])dp[m][j\; +\; 不同的]\; =\; min(dp[m][j\; +\; 不同的],\; 压缩过的相同的字符串的长度\; +\; dp[i\; -\; 1][j])$

这里我们可以拿图片解释一下

代码实现

class Solution {
public:
    int count(int n) {
        if (n == 1) return 1;
        if (n < 10) return 2;
        if (n < 100) return 3;
        return 4;
    }
//     计算占的位数
    int compressString(string s, int k) {
        int len = s.size();
        vector<vector<int>> dp(len + 1, vector<int>(k + 1, INT_MAX >> 1));
        dp[0][0] = 0;
//         dp数组的定义和初始化
        for (int i = 1; i <= len; i++) {
//             遍历每一个位置
            for (int j = 0; j <= i && j <= k; j++) {
//                 首先我们删除的元素，一定是要小于等于我们的当前的长度，并且小于我们题目中给定的可以最大删除的长度
                if (j < k) dp[i][j + 1] = min(dp[i][j + 1], dp[i - 1][j]);
//                 如果我们还可以继续删除，我们根据我们退出来的dp公式，这里怕数组越界所以我们统一把j -> j + 1
                int sameCharater = 0, differentCharater = 0;
//                 这个是寻找我们后面跟我们当前第i位字符有多少一样多少不一样，需要删除多少
                for (int m = i; m <= len; m++) {
//                     从当前位置向后遍历
                    s[m - 1] == s[i - 1] ? sameCharater += 1 : differentCharater += 1;
//                     判断两种情况进行增加的操作
                    if (j + differentCharater > k) break;
//                     如果我们现在需要的删除次数加上我们已经删除的次数大于了我们总共的次数，我们直接不用继续向后判断了
                    dp[m][j + differentCharater] = min(dp[m][j + differentCharater], count(sameCharater) + dp[i - 1][j]);
//                     否则的话，我们第m位删除了j + 不同的字符的次数，就是看我们当前这位和我们删除之后我们当前后面的长度加上原来的取一个最小值
                }
            }
        }
        return dp[len][k];
//         返回最后的答案
    }
};

时空复杂度分析

时间复杂度： $O(k\ast n^2)O(k\; *\; n\; ^\; 2)$

理由如下：首先我们的第一层循环的次数是字符串的大小$nn$，第二层判断删除的次数实际是$kk$次，第三层是向后查找也是跟字符串大小$nn$相关，所以最后得到时间复杂度是$O(k\ast n^2)O(k\; *\; n\; ^\; 2)$

空间复杂度： $O(n\ast k)O(n\; *\; k)$

理由如下：我们开辟的空间第一维跟我们的字符串大小相关，第二位跟我们删除的次数相关