3333. 找到初始输入字符串 II

发表于 分类于 阅读次数： Waline： 本文字数： 805 阅读时长 ≈ 3 分钟

考点

  • 多重背包
  • 前缀和
  • 滑动窗口
  • 乘法原理

思路

按相同字母进行划组，每个组至少得有一个字母，

那么假设某个组的字母个数为cnt[i]，那么它可以删0 ~ cnt[i] - 1个，最多可以删word.size() - k个

经典的多重背包裸题，可以得到下面的超时代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
 public:
  int possibleStringCount(string word, int k) {
    const int mod = 1e9 + 7;
    int cnt[500005], n = 0, m = word.size() - k;
    memset(cnt, 0, sizeof(cnt));
    // 双指针统计每个段落的可删减个数
    for (int i = 0; i < word.size();) {
      int j = i;
      while (j < word.size() && word[j] == word[i]) j++;
      cnt[n++] = j - i;
      i = j;
    }
    long long f[500005];
    memset(f, 0, sizeof(f));
    f[0] = 1;
    // 遍历每个段落，滑动窗口做DP
    for (int i = 0; i < n; ++i) {
      int c = cnt[i];
      long long sum = 0, old[500005];
      memcpy(old, f, sizeof(old));
      for (int j = 0; j <= m; ++j) {
        sum = (sum + old[j]) % mod;
        if (j - c >= 0) sum = (sum - old[j - c] + mod) % mod;
        f[j] = sum;
      }
    }
    // 求和
    long long sum = 0;
    for (int i = 0; i <= m; ++i) sum = (sum + f[i]) % mod;
    return sum;
  }
};

超时的核心原因就是背包容量过大，即m = word.size() - k这一段，5e5级别的可怕

正难则反，考虑逆事件

每个组的字母至少得有一个，那么每个组的字母个数应当是1 ~ cnt[i]个，即cnt[i]个可能性，根据乘法原理，总共的可能性就是所有的cnt[i]的总乘积

题目要求每个组的字母至少得有一个的情况下，总长度要大于等于K，逆事件就是小于等于K-1

为了方便实现，每个组的可能性都减去1，

即[1, cnt[i]]的闭区间变成[0, cnt[i] - 1]，那么背包总大小变成K - 1 - n

可以得到下面的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
 public:
  int possibleStringCount(string word, int K) {
    const int mod = 1e9 + 7;
    int cnt[500005], n = 0;
    long long T = 1;
    memset(cnt, 0, sizeof(cnt));
    // 双指针统计每个段落的可删减个数
    for (int i = 0; i < word.size();) {
      int j = i;
      while (j < word.size() && word[j] == word[i]) j++;
      cnt[n++] = j - i;
      T = T * (j - i) % mod;
      i = j;
    }
    long long f[2005];
    memset(f, 0, sizeof(f));
    f[0] = 1;
    int m = K - 1 - n;
    // 遍历每个段落，滑动窗口做DP
    for (int i = 0; i < n; ++i) {
      int c = cnt[i];
      long long sum = 0, old[2005];
      memcpy(old, f, sizeof(old));
      for (int j = 0; j <= m; ++j) {
        sum = (sum + old[j]) % mod;
        if (j - c >= 0) sum = (sum - old[j - c] + mod) % mod;
        f[j] = sum;
      }
    }
    // 求和
    long long sum = 0;
    for (int i = 0; i <= m; ++i) sum = (sum + f[i]) % mod;
    return (T-sum+mod)%mod;
  }
};

去掉memcpy和加上滚动数组，得到最终的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
 public:
  int possibleStringCount(string word, int K) {
    const int mod = 1e9 + 7;
    int cnt[500005], n = 0;
    long long T = 1;
    memset(cnt, 0, sizeof(cnt));
    // 双指针统计每个段落的可删减个数
    for (int i = 0; i < word.size();) {
      int j = i;
      while (j < word.size() && word[j] == word[i]) j++;
      cnt[n++] = j - i;
      T = T * (j - i) % mod;
      i = j;
    }
    long long f[2][2005];
    memset(f, 0, sizeof(f));
    f[0][0] = 1;
    int m = K - 1 - n;
    // 遍历每个段落，滑动窗口做DP
    for (int i = 0; i < n; ++i) {
      int c = cnt[i];
      long long sum = 0;
      for (int j = 0; j <= m; ++j) {
        sum = (sum + f[i & 1][j]) % mod;
        if (j - c >= 0) sum = (sum - f[i & 1][j - c] + mod) % mod;
        f[i + 1 & 1][j] = sum;
      }
    }
    // 求和
    long long sum = 0;
    for (int i = 0; i <= m; ++i) sum = (sum + f[n & 1][i]) % mod;
    return (T - sum + mod) % mod;
  }
};